刷题小组|倒计时4天：二叉树的层序遍历
题目
今天的题目是：二叉树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
来这里提交一下你的解答吧~https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
解题思路（BFS）
DFS（深度优先搜索）和 BFS（广度优先搜索），在实际使用中，我们用 DFS 的时候远远多于 BFS。
如果我们使用 DFS/BFS 只是为了遍历一棵树、一张图上的所有结点的话，那么 DFS 和 BFS 的能力没什么差别，我们当然更倾向于更方便写、空间复杂度更低的 DFS 遍历。不过，某些使用场景是 DFS 做不到的，只能使用 BFS 遍历，比如：「层序遍历」、「最短路径」。
首先我们看一下DFS和BFS代码的比较：
-
DFS遍历使用递归：
def DFS(self, root):
if not root:
return None
self.DFS(root.left)
self.DFS(root.right)
-
BFS遍历使用队列+迭代：
def BFS(self, root):
if not root:
return None
queue = [root]
while queue:
node = queue.pop(0)
if not node.left:
queue.add(node.left)
if not node.right:
queue.add(node.left)
只是比较两段代码的话，最直观的感受就是：DFS 遍历的代码比 BFS 简洁太多了！这是因为递归的方式隐含地使用了系统的栈，我们不需要自己维护一个数据结构。如果只是简单地将二叉树遍历一遍，那么 DFS 显然是更方便的选择。
虽然 DFS 与 BFS 都是将二叉树的所有结点遍历了一遍，但它们遍历结点的顺序不同。
那么在这道题中，要对二叉树进行层序遍历，即把二叉树分层，然后每一层从左到右遍历：
乍一看来，这个遍历顺序和 BFS 是一样的，我们可以直接用 BFS 得出层序遍历结果。
然而，层序遍历要求的输入结果和 BFS 是不同的。层序遍历要求我们区分每一层，也就是返回一个二维数组。而 BFS 的遍历结果是一个一维数组，无法区分每一层。
那么，怎么给 BFS 遍历的结果分层呢？我们首先来观察一下 BFS 遍历的过程中，结点进队列和出队列的过程为：节点N1先入队，其兄弟节点N2入队；然后按顺序N1出队，并将自己的左右孩子入队；兄弟节点N2再出队，并将自己的左右孩子入队...
截取 BFS 遍历过程中的某个时刻：
可以看到，此时队列中的结点是 3、4、5，分别来自第 1 层和第 2 层。这个时候，第 1 层的结点还没出完，第 2 层的结点就进来了，而且两层的结点在队列中紧挨在一起，我们无法区分队列中的结点来自哪一层。
因此，我们需要稍微修改一下代码，在每一层遍历开始前，先记录队列中的结点数量 n（也就是这一层的结点数量），然后一口气处理完这一层的 n 个结点。
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
# 特殊情况处理
if not root: return res
# 使用队列，初始时放入根节点
queue = [root]
while queue:
# 每一层的节点数量，要一起计算
n = len(queue)
# 用于存放节点的val给最终输出结果用
level = []
# 遍历某一层节点
for i in range(n):
# 将要处理的节点弹出
node = queue.pop(0)
# 将其val加入到level中
level.append(node.val)
# 如果有左右节点，则进入队列
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# 每一层节点都处理完，将接待你存入结果
res.append(level)
return res