https://oj.leetcode.com/problems/binary-tree-level-order-traversal/
Given a binary tree, return the level order traversal of its nodes‘ values. (ie, from left to right, level by level).
Solutions:
1. DFS
In fact, tree PreOrder() is Level order Traversal. Just add the level number.
class Solution:
# @param root, a tree node
# @return a list of lists of integers
def levelOrder(self, root):
if not root: return []
def PreOrder(root,level):
if root:
if level>=len(res):
res.append([])
res[level].append(root.getRootVal())
PreOrder(root.getLeftChild(),level+1)
PreOrder(root.getRightChild(),level+1)
res=[]
PreOrder(root,0)
return res
2.BFS
Exactly BFS. Note: BFS of tree is much simpler than that of Graph. No need to use visited array.
class Solution:
# @param root, a tree node
# @return a list of lists of integers
def levelOrder(self, root):
if not root: return []
def PreOrder(root,level):
if root:
if level>=len(res):
res.append([])
res[level].append(root.getRootVal())
PreOrder(root.getLeftChild(),level+1)
PreOrder(root.getRightChild(),level+1)
res=[]
PreOrder(root,0)
return res
Binary Tree Level Order Traversal
原文：http://www.cnblogs.com/idiotFRY/p/4107351.html