Description
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]
]
Solutions
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 not root:
return []
res = []
queue = [root]
cur_right = nxt_right = root
tmp = []
while queue:
node = queue.pop()
tmp.append(node.val)
if node.left:
queue.insert(0, node.left)
nxt_right = node.left
if node.right:
queue.insert(0, node.right)
nxt_right = node.right
if cur_right == node:
cur_right = nxt_right
res.append(tmp)
tmp = []
return res
# Runtime: 16 ms, faster than 95.42% of Python online submissions for Binary Tree Level Order Traversal.
# Memory Usage: 12.2 MB, less than 76.64% of Python online submissions for Binary Tree Level Order Traversal.
2. 迭代-size
import collections
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
res = []
queue = collections.deque()
queue.append(root)
while queue:
size = len(queue)
level_nodes = []
for _ in range(size):
node = queue.popleft()
if not node:
continue
level_nodes.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level_nodes)
return res
3. BFS 递归方法
# 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 not root:
return []
res = []
self.bfs(root, 0, res)
return res
def bfs(self, root, level, lis):
if not root:
return
# 如果 level 遍历到下一层就要补充一个新的列表保存下一层的结点
if level >= len(lis):
sub_lis = [root.val]
lis.append(sub_lis)
else:
lis[level].append(root.val)
self.bfs(root.left, level + 1, lis)
self.bfs(root.right, level + 1, lis)
# Runtime: 8 ms, faster than 99.95% of Python online submissions for Binary Tree Level Order Traversal.
# Memory Usage: 12.6 MB, less than 11.76% of Python online submissions for Binary Tree Level Order Traversal.