Given a binary tree, return the level order traversal of its nodes‘ values. (ie, from left to right, level by level).
For example:
Given binary tree[3,9,20,null,null,15,7],3 / 9 20 / 15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 递归方法
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root == None:
return []
dep = self.depth(root)
self.ret = [[] for i in range(dep)]
self.helper(root, 0)
return self.ret
def helper(self, node, dep):
if node == None:
return
self.ret[dep].append(node.val)
self.helper(node.left, dep + 1)
self.helper(node.right, dep + 1)
def depth(self, node):
if node == None:
return 0
return max(self.depth(node.left), self.depth(node.right)) + 1
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 迭代方法，栈
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root == None:
return []
stack, ret = [root], []
while stack:
level_value = []
next_level = []
for node in stack:
level_value.append(node.val)
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
ret.append(level_value)
stack = next_level
return ret
LeetCode 102. Binary Tree Level Order Traversal
原文：http://www.cnblogs.com/LiCheng-/p/6902352.html