102.二叉树的层序遍历
难度：中等
题目：
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层序遍历结果：
[
[3],
[9,20],
[15,7]
]
分析
BFS 解题分析
对于二叉树的层序遍历，一般都是使用BFS配合队列完成解题。
- 使用队列保存每层的所有节点（初始先入队根节点）
- 每次讲队列中的元素循环出队，获取该元素对应的val值
- 再把每个元素的非空左右子节点进入队列
- 循环2、3，即可得到每层的遍历。
DFS 解题分析
二叉树的前、中、后 顺序遍历，一般最简单的是使用深度优先，但层序遍历也可以通过DFS来解题。
麻烦一些的就是我们需要在DFS层级遍历的时候，根据当前深度进行保存，这里由于返回列表，所以
使用defaultdict来构造特殊的Hash表更为快捷。由于字典的key值为深度，是存在默认排序的，
所以递归返程回放回即可。
下面来分别看看一下两种解题...
解题1 广度优先算法：
from collections import deque
class Solution:
def levelOrder(self, root):
ret = []
queue = deque([root])
while queue:
tmp = []
for i in range(len(queue)):
point = queue.popleft()
if point:
tmp.append(point.val)
queue.append(point.left)
queue.append(point.right)
if tmp:
ret.append(tmp)
return ret
解题2 深度优先算法：
from collections import defaultdict
class Solution:
def levelOrder(self, root):
ret = defaultdict(list)
def dfs(base, level):
nonlocal ret
if base:
ret[level].append(base.val)
dfs(base.left, level + 1)
dfs(base.right, level + 1)
dfs(root, 0)
return list(ret.values())
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
