本文概览：本文以LeetCode题目"二叉树的层序遍历"为例，详细讲解BFS（广度优先搜索）的原理和实现，重点说明为什么用队列、队列如何保证层序、以及如何按层分组输出

一、题目

![[层序遍历题目.png]]

二、题目分析

题目要求按层从上到下、从左到右遍历二叉树，每一层的节点值放在一个列表中，最终返回一个列表的列表

比如：

1
2
3
4
5
6
7
        3
       / \
      9  20
        /  \
       15   7

输出：[[3], [9, 20], [15, 7]]

这道题的核心就是 BFS（广度优先搜索），也叫层序遍历。和之前用递归（DFS）"一根筋往下钻"不同，BFS 是"一层一层扫"

思路概览

Java 实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    // 根节点入队
    queue.offer(root);
    while (!queue.isEmpty()) {
        // 当前层的节点数
        int size = queue.size();
        List<Integer> list = new ArrayList<>();
        // 逐个处理当前层的节点
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            list.add(node.val);
            // 左孩子入队
            if (node.left != null) {
                queue.offer(node.left);
            }
            // 右孩子入队
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        res.add(list);
    }
    return res;
}

思路简要说明

  1. 用队列来控制遍历顺序，先进先出，保证从左到右
  2. 每轮开始前记录队列大小 size，这就是当前层的节点数
  3. 逐个出队当前层的节点，把值加入结果；同时把左右孩子依次入队
  4. 一轮结束，当前层处理完毕，队列里剩下的是下一层的节点

三、思路详解

DFS vs BFS：两种遍历思路

先回顾一下中序遍历（DFS），它的遍历路径是"一根筋往下钻"：

1
2
3
4
5
6
7
8
9
        3
       / \
      9  20
        /  \
       15   7

中序遍历（DFS）：9 → 3 → 15 → 20 → 7
  先一条路走到黑（9），再回退，再走到黑（15），再回退...
  深度优先，纵向展开

而层序遍历（BFS）是"一层一层扫"：

1
2
3
4
5
6
7
8
9
        3
       / \
      9  20
        /  \
       15   7

层序遍历（BFS）：[3] → [9, 20] → [15, 7]
  先扫第一层，再扫第二层，再扫第三层...
  广度优先，横向展开

DFS 是"先往深处走"，BFS 是"先往宽处走"。DFS 靠递归实现，BFS 靠队列实现

为什么用队列？

BFS 的核心数据结构是队列（Queue）。队列的特性是先进先出（FIFO），这正好满足"按层顺序处理"的需求

想一想：要按层遍历，就必须先处理上层的节点，再处理下层的节点。队列的先进先出保证了：

  • 当前层的节点先入队，所以先出队
  • 孩子节点后入队，所以等当前层都出完了，下一层才轮到出队

用一个形象的比喻：队列就像一条排队的通道。当前层的人在前面处理，处理完一个就把他的"孩子"（下一层的节点）排到队伍末尾。等前面这一批人都处理完了，下一批人自然就排到了队伍前面

整个流程可以概括为一句话：把当前层的节点依次出队，出队的同时把它们的孩子依次入队

怎么按层分组？

题目要求每一层的节点放在一个单独的列表中，所以关键问题是：怎么区分哪些节点属于同一层？

答案在于：每轮开始前，队列里恰好只有当前层的节点

为什么？因为上一轮出队时，把当前层的节点都出完了，只留下了它们的孩子们（即下一层的节点）。所以每轮开始时 queue.size() 就是当前层的节点数

这个 size 非常关键——它告诉我们这轮要出队几个节点。用 for 循环精确地出队 size 个节点，就不会多出下一层的节点

size 必须在 for 循环外记录。如果放在循环条件里用 queue.size()，因为循环中会往队列加入新节点（孩子），大小会不断变化，导致一轮处理了多层的节点

图解完整过程

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

初始：队列 = [3]

第 1 轮（处理第 1 层）：

当前队列大小 = 1，说明第 1 层有 1 个节点

1
2
3
4
5
6
7
队列：[3]

出队 3 → 加入结果 [3]
  3 有左孩子 9 → 入队
  3 有右孩子 20 → 入队

队列变为：[9, 20]

第 2 轮（处理第 2 层）：

当前队列大小 = 2，说明第 2 层有 2 个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
队列：[9, 20]

出队 9 → 加入结果 [3, 9]
  9 没有左孩子
  9 没有右孩子

队列变为：[20]

出队 20 → 加入结果 [3, 9, 20]
  20 有左孩子 15 → 入队
  20 有右孩子 7 → 入队

队列变为：[15, 7]

第 3 轮（处理第 3 层）：

当前队列大小 = 2，说明第 3 层有 2 个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
队列：[15, 7]

出队 15 → 加入结果 [3, 9, 20, 15]
  15 没有左孩子
  15 没有右孩子

队列变为：[7]

出队 7 → 加入结果 [3, 9, 20, 15, 7]
  7 没有左孩子
  7 没有右孩子

队列变为：[]（空）

队列空了，遍历结束。最终结果按层分组：[[3], [9, 20], [15, 7]]

可以看到，每一轮开始时队列中恰好是当前层的所有节点。这是因为上一轮出队当前层节点的同时，把它们的孩子（下一层节点）入队了。等当前层全部出队完毕，队列里就只剩下下一层的节点

入队顺序：先左后右

题目要求从左到右遍历，所以入队顺序必须是先左孩子后右孩子。因为队列是先进先出的，先入队的先出队，所以先入队左孩子就能保证同一层中左边的节点先被处理

如果先入队右孩子再入队左孩子，同一层的节点就会变成从右到左的顺序，不符合题目要求

复杂度分析

  • 时间复杂度：O(n)，每个节点恰好入队一次、出队一次
  • 空间复杂度：O(n)，队列中最多同时存放一层节点，最坏情况（完全二叉树最后一层）约为 n/2 个节点