广度优先遍历：层序、倒序层序与锯齿层序
摘要
深度优先遍历关注的是“沿一条路径先走到底”，而广度优先遍历关注的是“按层推进”。LeetCode 102、107、103 是二叉树 BFS 的核心入门题，看似只是把节点放进队列，实际考察的是另一种完全不同的思维模型：如何清晰地定义一层、如何在结果结构中保留层信息、以及当题目要求倒序或锯齿形输出时，应该修改遍历过程还是仅修改写入策略。本文会把这三道题抽象为同一个层序模板。
第 1 章 层序遍历为什么不是简单队列
1.1 真正的问题是“如何切层”
如果只把根节点入队，然后每次弹出一个节点、把左右孩子继续入队，你当然能按从上到下、从左到右的顺序看到所有节点。但题目要求的不是一个扁平序列，而是：
[
[第 0 层],
[第 1 层],
[第 2 层]
]所以 BFS 的关键不是“队列存在”，而是：在什么时候知道当前这一层结束了。
1.2 为什么每轮要先固定 size
层序遍历最经典的写法，是在每一轮开始时保存当前队列长度 size。这个 size 恰好就是当前层的节点数。
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
...
}理由非常朴素：
- 循环开始前，队列里全是当前层节点
- 当前层节点出队时，会把下一层节点加入队尾
- 如果不提前固定
size，当前层和下一层就会混在一起
这就是“切层边界”的本质。
第 2 章 LeetCode 102：标准层序遍历
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(level);
}
return result;
}这个模板以后会不断出现：最小深度、右视图、每层平均值、按层连接 next 指针，都可以从这里平移过去。
2.1 手动模拟
对于下面这棵树：
3
/ \
9 20
/ \
15 7队列变化如下：
初始: [3]
第 0 层 size=1 -> 弹出 3，加入 9、20 -> 结果 [3]
队列: [9,20]
第 1 层 size=2 -> 弹出 9、20，加入 15、7 -> 结果 [9,20]
队列: [15,7]
第 2 层 size=2 -> 弹出 15、7 -> 结果 [15,7]
队列: []第 3 章 LeetCode 107：自底向上的层序遍历
3.1 两种思路
LeetCode 107 和 102 的差别只有一点：最后输出从底层到顶层。
有两种处理方式：
- 正常层序遍历，最后整体反转结果
- 每层结果直接头插到链表头部
如果从工程可读性出发，第一种更直观。
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
Collections.reverse(result);
return result;
}3.2 为什么不需要改 BFS 本身
因为题目只改了“输出顺序”，没改“访问顺序”。访问节点仍然必须从上到下按层推进，只有结果展示反过来而已。这个判断很重要，它能避免你为了输出形式去破坏原有的清晰遍历逻辑。
第 4 章 LeetCode 103：锯齿层序遍历
4.1 难点不在队列，而在每层写入方向
锯齿层序要求：
- 第 0 层从左到右
- 第 1 层从右到左
- 第 2 层从左到右
- 依次交替
这里有两种常见误区：
- 试图改变孩子入队顺序
- 试图在奇数层反向遍历队列
实际上都没必要。队列仍然按正常层序维护即可，变化的是每层结果的写入方式。
4.2 用双端队列承载层结果
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean leftToRight = true;
while (!queue.isEmpty()) {
int size = queue.size();
Deque<Integer> level = new ArrayDeque<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (leftToRight) {
level.offerLast(node.val);
} else {
level.offerFirst(node.val);
}
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(new ArrayList<>(level));
leftToRight = !leftToRight;
}
return result;
}4.3 为什么“只改写入，不改遍历”更稳
因为节点的真实拓扑顺序没有变。第 1 层依然应该先处理左孩子再处理右孩子，只是最终这一层在结果里要从右往左呈现。把“遍历顺序”和“结果排列”解耦，是层序题很重要的习惯。
第 5 章 BFS 与 DFS 的边界
5.1 哪些题天然适合 BFS
- 最小深度：第一次遇到叶子节点即可返回
- 每层视角问题：右视图、层平均值、层最大值
- 横向连接问题：填充每个节点的下一个右侧节点指针
5.2 哪些题更适合 DFS
- 需要子树返回值汇总的题
- 需要根到叶路径状态的题
- 需要利用后序时机更新全局答案的题
BFS 不是 DFS 的“另一种写法”
BFS 解决的是分层问题，DFS 解决的是分支递归问题。两者都能遍历整棵树，但适用的中间状态完全不同。
下一篇预告
03 二叉树结构判定：相同树、对称树与平衡二叉树 会进一步展示递归函数返回值该如何设计。尤其是平衡二叉树这道题，会让你第一次真正感受到“后序返回高度”的力量。