层序遍历
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历，只不过应用在二叉树上。
已刷（都可以通过层次遍历实现）：
226.翻转二叉树
- 对称二叉树
102.二叉树的层序遍历
107.二叉树的层次遍历II
199.二叉树的右视图
637.二叉树的层平均值
429.N叉树的层序遍历
515.在每个树行中找最大值
116.填充每个节点的下一个右侧节点指针
117.填充每个节点的下一个右侧节点指针II
104.二叉树的最大深度
111.二叉树的最小深度
222.完全二叉树的节点个数
层次遍历代码模板
class Solution:
"""二叉树层序遍历迭代解法"""
def levelOrder(self, root: TreeNode) -> List[List[int]]:
results = []
if not root:
return results
from collections import deque
que = deque([root])
while que:
size = len(que)
result = []
for _ in range(size):
cur = que.popleft()
result.append(cur.val)
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
results.append(result)
return results
# 递归法
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
def helper(root, depth):
if not root: return []
if len(res) == depth: res.append([]) # start the current depth
res[depth].append(root.val) # fulfil the current depth
if root.left: helper(root.left, depth + 1) # process child nodes for the next depth
if root.right: helper(root.right, depth + 1)
helper(root, 0)
return res
