#102
中等
中频
队列二叉树的层序遍历
这是一道围绕树、二叉树、广度优先搜索展开的高频练习。建议先掌握「队列」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
树
二叉树
广度优先搜索
题目分析
给你一棵二叉树，要求按从上到下、从左到右的顺序，逐层返回每一层节点的值。
最终答案是一个二维列表，每个子列表对应树的一层。
一句话概括：
用队列一层一层把树的节点取出来。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：用队列维护当前层待处理节点，每轮先固定层大小，再把这一层完整取出来。
推荐代码
推荐解法：队列
时间复杂度： O(n)
空间复杂度： O(n)
核心思路： 用队列维护当前层待处理节点，每轮先固定层大小，再把这一层完整取出来。
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<List<Integer>> result = new ArrayList<>();
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>();
int queueSize = queue.size();
for (int i = 0; i < queueSize; i++) {
TreeNode temp = queue.poll();
level.add(temp.val);
//左子树不为空，队列中添加左
if (temp.left != null) {
queue.add(temp.left);
}
//右子树不为空，队列中添加右
if (temp.right != null) {
queue.add(temp.right);
}
}
result.add(level);
}
return result;
}结构化讲解
面试时怎么讲
开场思路
这题是树上的按层遍历，我会直接用 BFS。核心数据结构是队列，因为它天然适合一层一层往外扩。
核心过程
- 先把根节点放入队列，表示第一层待处理节点。
- 每轮先记录当前队列长度，这个长度就是当前层的节点数。
- 只处理这么多个节点：出队、记录节点值、再把左右孩子加入队列。
- 这一轮结束后，把当前层收集到的列表放进最终答案。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(n)。
面试补一句：层序遍历最关键的动作不是“用队列”，而是“先固定当前层大小”。
核心思路
层序遍历的本质是树上的 BFS。队列负责保证“先到先处理”，而每轮提前记录队列长度，负责把当前层和下一层分开。
步骤讲解
1
根节点先入队
如果根节点存在，先把它放进队列，作为第一层的起点。
为什么这样做：队列里保存的是“下一批要处理的节点”，没有起点就无法按层展开。
对应代码提示：queue.offer(root);
2
先固定当前层节点数
每次进入 while 循环，先记录 queue.size() 作为当前层的节点个数。
为什么这样做：遍历过程中会不断把孩子节点加入队列，如果不先固定大小，就会把下一层也混进当前层。
对应代码提示：int size = queue.size();
3
按固定次数取出这一层
循环 size 次，把这一层所有节点依次出队，并把它们的值加入当前层答案。
为什么这样做：这样可以保证每一轮只处理一整层，而不是把整棵树一次性打平。
对应代码提示：TreeNode node = queue.poll(); level.add(node.val);
4
把下一层孩子入队
当前节点处理完后，如果左右孩子存在，就依次加入队列。
为什么这样做：这些孩子节点正好构成下一轮要处理的那一层。
对应代码提示：if (node.left != null) queue.offer(node.left);
5
本层结束后加入结果
当固定的 size 次循环结束，说明这一层已经处理完，把 level 放进答案。
为什么这样做：题目要求按层返回二维数组，所以每一层都要单独收集。
对应代码提示：answer.add(level);
易错点
没有先记录 size
如果直接在 while (!queue.isEmpty()) 中不停出队并入队，当前层和下一层会混在一起，结果不再是按层划分。
正确理解：每轮开始先固定
size = queue.size()，再只处理这么多个节点。忘记处理空树
根节点为 null 时，如果直接入队或访问节点值，会出现空指针问题。
正确理解：函数开始先判断
root == null，直接返回空列表。把 queue 当成栈使用
如果不是先进先出，而是后进先出，遍历顺序就会从 BFS 变成 DFS，结果不再是层序遍历。
正确理解：必须使用队列语义，始终保持先入队的节点先出队。
复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(n)
比其他方案更好在哪里：比先 DFS 再按深度分桶的思路更直接，天然就是一层一层展开。
适用判断：只要题目要求按层遍历、按层统计或逐层扩散，优先考虑 BFS + 队列。
额外提醒
- 树上按层处理时，队列就是最自然的第一反应。
- 真正决定结果是否正确的，不是入队动作，而是每轮先固定本层大小。
动画演示
如果你还没完全看懂，可以展开动画演示。
队列动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
队列动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
二叉树层序遍历
当前状态：
准备就绪，点击开始查看层序遍历过程
步骤：0
遍历结果：
尚未开始遍历
当前队列：
队列为空
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。