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())
