Binary Tree Level Order Traversal 是 LeetCode Hot 100 里面一道非常经典的二叉树遍历题。
这道题和前面的前序遍历、中序遍历、后序遍历不太一样。 因为前面那些题本质上都属于 深度优先遍历（DFS），而这道题考察的是另一种非常重要的树遍历方式：
广度优先遍历（BFS）
也就是我们常说的：
一层一层地遍历二叉树。
你给出的这份 Java 代码，使用的是这道题最标准、最经典的一种写法：
队列 + 按层处理
-
用队列维护当前层待访问的节点
-
每次先记录当前层节点个数
-
逐个弹出这一层的节点，并把它们的左右孩子加入队列
-
这样就能保证每次循环处理的刚好是一整层
本文就结合这段代码，系统地讲一下这道题的思路。
题目介绍
给你一棵二叉树的根节点 root，要求你返回它的 层序遍历结果。
所谓层序遍历，就是按照从上到下、从左到右的顺序，一层一层地访问节点。
例如下面这棵树：
3
/ \
9 20
/ \
15 7
它的层序遍历结果就是：
[
[3],
[9,20],
[15,7]
]
因为：
-
第 1 层只有
3 -
第 2 层是
9和20 -
第 3 层是
15和7
题目要求返回的是一个二维列表，其中每个子列表对应树的一层。
示例
示例 1
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2
输入：root = [1]
输出：[[1]]
示例 3
输入：root = []
输出：[]
空树没有任何节点，所以结果为空列表。
这道题和前面的树遍历有什么区别？
前面的树遍历题，比如：
-
前序遍历
-
中序遍历
-
后序遍历
它们更像是沿着树一直往下走，再递归回来，本质上属于：
深度优先搜索（DFS）
而这道题不一样，它要求的是：
先把同一层全部访问完，再去下一层。
这是一种典型的：
广度优先搜索（BFS）
所以这道题最关键的，不是递归顺序，而是：
如何维护“当前层有哪些节点”。
这就是为什么队列会成为这道题最自然的数据结构。
为什么适合用队列？
因为队列天然符合 BFS 的访问顺序：
-
先进入队列的节点，先被处理
-
当前层节点出队后，再把下一层节点按顺序入队
这样就能保证遍历顺序是：
从上到下、从左到右
这正好和层序遍历要求一致。
如果你把树想象成一圈圈向外扩散的层，那么队列就像一个“等待区”，始终保存着下一批要访问的节点。
核心思路
这道题的标准做法可以概括成下面几步：
第一步：把根节点放进队列
如果根节点不为空，就先入队。
第二步：每次处理一整层
当前队列中的所有节点，正好就是当前层的全部节点。 所以在每次 while 循环开始时，先记录一下：
queue.size()
这个值就是“这一层有多少个节点”。
第三步：把这一层的节点依次弹出
每弹出一个节点：
-
把它的值加入当前层结果列表
-
如果它有左孩子，就把左孩子加入队列
-
如果它有右孩子，就把右孩子加入队列
注意：加入队列的是下一层节点。
第四步：当前层处理完后，把结果加入总答案
然后继续处理下一层。
这正是你代码里的完整逻辑。
Java 代码
下面是你给出的代码，我这里保留原始逻辑，并加上注释：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
// 根节点不为空时，先入队
if (root != null) queue.add(root);
while (!queue.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
// 当前队列大小，就是这一层的节点个数
for (int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
tmp.add(node.val);
// 把下一层节点加入队列
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
// 当前层遍历完成，加入答案
res.add(tmp);
}
return res;
}
}
代码拆解
这段代码是二叉树层序遍历最经典的 BFS 模板。 下面一步一步来看。
1. 为什么先创建队列和结果集？
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
queue
用来做层序遍历的核心数据结构。 它负责保存“接下来要访问的节点”。
res
用来保存最终答案。 因为题目要求每一层单独存成一个列表，所以 res 是一个二维列表。
2. 为什么根节点不为空时先入队？
if (root != null) queue.add(root);
因为层序遍历一定是从根节点开始的。
如果树为空，那队列就保持空，后面的 while 循环不会进入，最终返回空列表。 如果树不为空，那根节点就是第一层唯一的节点，所以应该先加入队列。
这一步其实就是 BFS 的起点初始化。
3. 为什么 while (!queue.isEmpty()) 表示逐层遍历？
while (!queue.isEmpty()) {
只要队列不为空，就说明还有节点没处理完。
由于每一轮循环都会把“当前层”的节点全部弹出来，并把“下一层”的节点加进去，所以这个 while 循环本质上就是：
一层一层地向下推进。
每次循环，对应的就是处理树的一层。
4. 为什么每轮都要新建一个 tmp？
List<Integer> tmp = new ArrayList<>();
因为题目要求：
-
每一层的节点值单独放在一个列表里
所以当前层开始处理时，需要先准备一个新的列表 tmp，专门用来收集这一层的所有节点值。
等这一层处理完，再把 tmp 加入总答案 res。
5. 为什么 for (int i = queue.size(); i > 0; i--) 这样写？
for (int i = queue.size(); i > 0; i--) {
这是整道题最关键的一句。
原因在于：
在进入这一层之前，队列中的所有节点，正好就是当前层的节点。
例如当前队列里有 2 个节点，那说明这一层就有 2 个节点。 所以先把这个数量记下来，然后循环处理恰好这么多个节点。
为什么不能直接写：
for (int i = 0; i < queue.size(); i++)
因为在循环过程中，我们还会不断把下一层节点加入队列。 如果直接动态使用 queue.size()，那队列大小会变化，当前层和下一层就会混在一起。
所以一定要在循环开始前，先固定住当前层节点数。
你这里写成：
for (int i = queue.size(); i > 0; i--)
本质上就是“处理当前层的固定数量节点”，这是一种非常经典的 BFS 按层写法。
6. 为什么弹出节点后先加入 tmp，再把左右孩子入队？
TreeNode node = queue.poll();
tmp.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
这三步分别表示：
第一步：从队列中取出当前层节点
TreeNode node = queue.poll();
第二步：把当前节点值记录到本层结果里
tmp.add(node.val);
第三步：把它的左右孩子加入队列
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
注意这里加入队列的不是当前层，而是：
下一层节点
这就是 BFS 的关键： 当前层出队，下一层入队。
7. 为什么每层结束后要 res.add(tmp)？
res.add(tmp);
因为当前 for 循环结束时，说明这一层的所有节点都已经处理完了。 所以此时 tmp 中保存的就是完整的一层结果。
把它加入 res 后，就相当于把这一层正式收进最终答案。
手动模拟一遍
我们用经典例子来走一遍：
3
/ \
9 20
/ \
15 7
初始状态
队列中先放入根节点：
queue = [3]
res = []
第 1 轮 while
当前：
queue.size() = 1
说明这一层有 1 个节点。
处理节点 3
-
弹出
3 -
加入当前层列表：
tmp = [3] -
把它的左右孩子
9、20入队
此时：
queue = [9, 20]
tmp = [3]
这一层结束后：
res = [[3]]
第 2 轮 while
当前：
queue.size() = 2
说明这一层有 2 个节点。
处理节点 9
-
弹出
9 -
tmp = [9] -
9没有左右孩子，不入队
处理节点 20
-
弹出
20 -
tmp = [9,20] -
把
15、7入队
此时：
queue = [15, 7]
tmp = [9,20]
这一层结束后：
res = [[3], [9,20]]
第 3 轮 while
当前：
queue.size() = 2
说明这一层还是 2 个节点。
处理节点 15
-
弹出
15 -
tmp = [15]
处理节点 7
-
弹出
7 -
tmp = [15,7]
这一层结束后：
res = [[3], [9,20], [15,7]]
队列为空，遍历结束。
最终答案就是：
[[3],[9,20],[15,7]]
为什么这个方法是正确的？
因为 BFS 的本质就是按“距离起点的层数”来访问节点。
对于二叉树来说：
-
根节点是第 0 层
-
根节点的左右孩子是第 1 层
-
再往下就是第 2 层
而队列的先进先出特性，正好可以保证：
-
当前层的节点先被处理
-
它们的孩子被按顺序加入队列
-
等当前层处理完后，队列里就只剩下一整层的下一层节点
再配合“每轮固定处理 queue.size() 个节点”，就能精确地把每一层分开。
所以这个方法一定可以正确得到层序遍历结果。
复杂度分析
假设二叉树一共有 n 个节点。
时间复杂度
每个节点都会被：
-
入队一次
-
出队一次
并且每次处理都是常数操作，所以总时间复杂度是：
O(n)
空间复杂度
队列中在最坏情况下可能会同时存放某一层的所有节点。 所以空间复杂度取决于树某一层的最大宽度。
最坏情况下可以写作：
O(n)
这道题真正想考什么？
这道题表面上是在做树遍历，但本质上是在考察：
第一，是否区分 DFS 和 BFS
前面的树递归题更多是在练 DFS。 而这题明确要求按层遍历，所以更适合 BFS。
第二，是否会用队列处理“按层”
很多人知道 BFS 要用队列，但不一定能立刻想到：
为了区分层，必须先记录当前层节点数。
这其实是层序遍历里最经典的技巧。
第三，是否理解“当前层”和“下一层”如何通过队列衔接
当前层节点出队的同时，把下一层节点入队，正是 BFS 的核心运作方式。
这题还有别的写法吗？
有。
除了现在这种最经典的 队列 BFS 写法之外，也可以用 DFS 来做层序遍历。 思路通常是：
-
递归遍历时带上当前深度
level -
当访问到某个节点时，把它放进
res[level]中
这样也能得到层序结果。
不过从题目本意和写法直观程度来说，BFS 队列解法仍然是最自然、最推荐的。
和“二叉树的右视图”“锯齿形层序遍历”有什么关系？
这几道题其实是同一套 BFS 模板的变形。
二叉树层序遍历
每层把所有节点按顺序收集起来。
二叉树右视图
每层只取最后一个节点。
锯齿形层序遍历
仍然是一层一层遍历，只是奇偶层的输出顺序不同。
所以这道题其实是很多“按层处理二叉树”题目的基础模板。
总结
这道题的核心思想可以概括成一句话：
使用队列做广度优先搜索，每次固定处理当前层的所有节点，并把下一层节点加入队列，从而实现按层遍历。
具体步骤就是：
-
根节点不为空时先入队
-
当队列不为空时，先记录当前层节点数
-
依次弹出这一层的节点，把它们的值加入当前层列表
-
同时把这些节点的左右孩子加入队列
-
当前层处理完后，把这一层结果加入答案
这样就能得到完整的层序遍历结果。
这是一道非常经典、也非常值得认真掌握的二叉树题。 因为它会让你真正体会到：
-
BFS 和 DFS 在树上的区别
-
队列在层序遍历里为什么如此自然
-
“先记录当前层大小”为什么是按层遍历的关键技巧
把这道题真正吃透之后，再去看：
-
二叉树的右视图
-
二叉树锯齿形层序遍历
-
最小深度
-
N 叉树层序遍历
这些 BFS 树题时，你会明显更容易抓住套路。
