102. Binary Tree Level Order Traversal
难度: 中等
刷题内容
原题连接
- https://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).
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]
]
解题方案
思路 1
递归
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
res = []
self.recurHelper(root, 0, res)
return res
def recurHelper(self, root, level, res):
if not root: return
if len(res) < level + 1:
res.append([])
res[level].append(root.val)
self.recurHelper(root.left, level+1, res)
self.recurHelper(root.right, level+1, res)
思路 2
迭代，利用curLevel和nextLevel来记录，然后按层append.
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
res, cur_level = [], [root]
while cur_level:
next_level, tmp_res = [], []
for node in cur_level:
tmp_res.append(node.val)
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
res.append(tmp_res)
cur_level = next_level
return res
