9.3　广度优先遍历与层序

学习目标：学完本节，你能

• 用队列实现层序遍历，并说清为什么必须用队列而不是栈；
• 写出"按层分组"的模板，理解其中一个关键的行；
• 说出 BFS 相对 DFS 的独特优势 —— 以及它在什么问题上更快。

先修：9.2（深度优先遍历）、5.2（队列）。 固定术语：广度优先、层序遍历、BFS。 环境与版本：.NET 8 / C# 12。 预计阅读：28 分钟。

一、直觉：水波纹 vs 钻探

深度优先（DFS）像钻探 —— 认准一个方向一直往下钻，钻到底了再退回来换个方向。

广度优先（BFS）像水波纹 —— 从中心开始，一圈一圈向外扩散。

  DFS:  1 → 2 → 4 → 7 →（退回）→ 5 →（退回）→ 3 → 6
        一条路走到底

  BFS:  第 0 层: 1
        第 1 层: 2 3
        第 2 层: 4 5 6
        第 3 层: 7
        一层一层往外

这个"一圈一圈"的顺序，正好对应树的"层"。所以二叉树的 BFS 也叫层序遍历（Level-Order Traversal）。

二、为什么必须用队列

先看代码：

/// <summary>最基础的层序遍历：按层从上到下、每层从左到右访问所有节点。</summary>
static List<int> LevelOrder(TreeNode? root)
{
    var result = new List<int>();
    if (root == null) return result;

    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        var node = queue.Dequeue();        // 从队首取出
        result.Add(node.Value);

        if (node.Left != null) queue.Enqueue(node.Left);     // 孩子从队尾加入
        if (node.Right != null) queue.Enqueue(node.Right);
    }
    return result;
}

和 DFS 对比一下：

"为什么 BFS 用队列、DFS 用栈"，本质上就是 5.1/5.2 节讲的 LIFO 和 FIFO 的区别。

DFS 用栈：把两个孩子压栈后，后压的（左孩子）先被取出 —— 于是"先往左下走"，这就是深度优先。

BFS 用队列：两个孩子入队后，先入队的（左孩子）先被取出 —— 但更重要的是，当前层的所有节点都排在下一层的前面，所以是"一层一层"的。

实测：

  层序遍历（BFS）: 1 2 3 4 5 6 7

对比 9.2 节的三种 DFS：

  前序（DFS）: 1 2 4 5 3 6 7
  层序（BFS）: 1 2 3 4 5 6 7    ← 注意这里 2 之后直接是 3（第二层）

三、按层分组：一个关键的行

基础的层序遍历把"层"的信息丢掉了。如果业务需要"每一层分别处理"，就要分组：

/// <summary>按层分组：返回每一层的节点值。</summary>
static List<List<int>> LevelOrderGrouped(TreeNode? root)
{
    var result = new List<List<int>>();
    if (root == null) return result;

    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        int levelSize = queue.Count;       // ★ 关键：先记住「这一层有多少个」
        var currentLevel = new List<int>();

        for (int i = 0; i < levelSize; i++)   // 只处理这一层的节点
        {
            var node = queue.Dequeue();
            currentLevel.Add(node.Value);
            if (node.Left != null) queue.Enqueue(node.Left);
            if (node.Right != null) queue.Enqueue(node.Right);
        }
        result.Add(currentLevel);
    }
    return result;
}

int levelSize = queue.Count; 这一行是全部的关键。

为什么？

因为在遍历这一层的过程中，我们会把下一层的节点加到队列里。如果不提前记住"这一层有多少个"，就没法知道该在哪里停下来。

处理第 1 层时：
  队列开始: [2, 3]           levelSize = 2
  取出 2，把 4、5 加进去 -> [3, 4, 5]
  取出 3，把 6 加进去    -> [4, 5, 6]
  循环 2 次结束（因为 levelSize = 2）
  此时队列里正好是第 2 层: [4, 5, 6]  ✓

实测：

  按层分组：
    第 0 层: 1
    第 1 层: 2 3
    第 2 层: 4 5 6
    第 3 层: 7

如果没有 levelSize 这一行，你会得到一个"大杂烩" —— 只能知道所有节点的 BFS 顺序，分不出层。

这是 BFS 类题目最常见的考点。

另一种写法（带层号入队）：

var queue = new Queue<(TreeNode Node, int Level)>();
queue.Enqueue((root, 0));
while (queue.Count > 0)
{
    var (node, level) = queue.Dequeue();
    // 用 level 做任何事
    if (node.Left != null) queue.Enqueue((node.Left, level + 1));
    if (node.Right != null) queue.Enqueue((node.Right, level + 1));
}

实测输出：

  带层号：1(L0)  2(L1)  3(L1)  4(L2)  5(L2)  6(L2)  7(L3)

两种写法对比：

写法	优点	缺点
levelSize	不需要额外空间、不用元组	需要在循环里"记住"这个数
带层号	直观	每个节点多存一个 int；而且队列里会同时存在不同层的节点

推荐 levelSize 写法 —— 它更省内存，而且"层边界"这个概念更清晰。

四、BFS 的经典应用

应用 1：右视图

"从树的右侧看过去，能看到哪些节点"—— 就是"每一层最右边的那个"。

static List<int> RightSideView(TreeNode? root)
{
    var result = new List<int>();
    if (root == null) return result;

    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        int levelSize = queue.Count;
        for (int i = 0; i < levelSize; i++)
        {
            var node = queue.Dequeue();
            if (i == levelSize - 1) result.Add(node.Value);   // 这一层最后一个
            if (node.Left != null) queue.Enqueue(node.Left);
            if (node.Right != null) queue.Enqueue(node.Right);
        }
    }
    return result;
}

实测：1 3 6 7

验证：第 0 层只有 1；第 1 层最右是 3；第 2 层最右是 6（4、5、6 里最右）；第 3 层只有 7 ✓

这个模式的通用性：if (i == levelSize - 1) 可以换成任何"只对每层特定位置生效"的条件（比如 i == 0 就是左视图）。

应用 2：求最小深度 —— BFS 在这里比 DFS 快

这是 BFS 相对 DFS 最有说服力的优势。

/// <summary>最小深度：用 BFS —— 第一次遇到叶子就可以停。</summary>
static int MinDepthBFS(TreeNode? root)
{
    if (root == null) return 0;

    var queue = new Queue<(TreeNode Node, int Depth)>();
    queue.Enqueue((root, 1));

    while (queue.Count > 0)
    {
        var (node, depth) = queue.Dequeue();
        if (node.Left == null && node.Right == null) return depth;   // 第一个叶子
        if (node.Left != null) queue.Enqueue((node.Left, depth + 1));
        if (node.Right != null) queue.Enqueue((node.Right, depth + 1));
    }
    return 0;
}

实测对比（一棵"左深右浅"的树，6 个节点）：

         1
        / \
       2   9   <- 9 是叶子，深度只有 1
      /
     3
    /
   4
  /
 5

    这棵树共 6 个节点
    BFS 找最小深度只访问了 3 个节点就停了（找到 9 就返回）
    DFS 必须访问全部 6 个节点

为什么 BFS 更快？

BFS 是"一层一层"访问的，所以第一次遇到叶子，那个叶子一定是【最浅】的 —— 可以立刻返回。

DFS 必须先走完整棵树，才能比较出哪个叶子最浅 —— 因为它可能先钻到左边 5 层深的地方，才发现右边第 2 层就有个叶子。

这条性质有个重要的推广：

在"边权都相同"的图上，BFS 找到的路径一定是【最短路径】。

因为 BFS 是按"距离起点的步数"一层层扩散的 —— 第一次到达某个节点时，走的一定是最少步数。

这就是第 12 章"无权图最短路径"用 BFS 的原因。

应用 3：其他常见场景

五、BFS vs DFS：完整对比

  维度               | BFS（层序）              | DFS（前/中/后序）
--------------------------------------------------------------------------
  数据结构            | 队列                     | 栈（递归隐含）
  访问顺序            | 一层一层                   | 一条路走到底
  空间                | O(最宽的一层)              | O(树高)
  适合                | 最短路径、层相关信息          | 路径、子树信息、回溯

空间开销的差异值得单独说：

"哪个更省空间"完全取决于树的形状：

• 宽而浅的树：BFS 要存一整层（可能几十万个节点），DFS 只存一条路径 —— DFS 省
• 窄而深的树（比如链）：BFS 队列里始终只有一两个节点，DFS 要递归 n 层 —— BFS 省

没有绝对的优劣，要看数据和问题。

选择的判断依据：

六、练习

练习 9.3.1（手写层序） 对下面这棵树，写出层序遍历的结果，并给出每一层的节点：

              A
            /   \
           B     C
          / \     \
         D   E     F
            / \
           G   H

练习 9.3.2（代码填空） 下面这个"求每层平均值"的代码中，横线处应该填什么？

static List<double> LevelAverages(TreeNode? root)
{
    var result = new List<double>();
    if (root == null) return result;

    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        int size = ______;          // (a)
        double sum = 0;
        for (int i = 0; i < size; i++)
        {
            var node = queue.Dequeue();
            sum += node.Value;
            if (node.Left != null) queue.Enqueue(node.Left);
            if (node.Right != null) queue.Enqueue(node.Right);
        }
        result.Add(______);         // (b)
    }
    return result;
}

练习 9.3.3（判断） 判断对错并说明理由： (a) 层序遍历用的是栈。 (b) BFS 一定比 DFS 省空间。 (c) 求"最小深度"用 BFS 比 DFS 快，是因为 BFS 的时间复杂度更低。

练习 9.3.4（应用） 一个社交网络要计算"你和某个人之间的最短关系链"（比如"你 → 朋友 → 朋友的朋友"）。 (a) 这应该用 BFS 还是 DFS？ (b) 为什么？ (c) 如果每条关系链有不同的"亲密度权重"（比如家人 1、同事 3、陌生人 10），求"亲密度总和最小"的链，还能用 BFS 吗？

练习 9.3.5（挑战·判断完全二叉树） 用 BFS 判断一棵二叉树是否是完全二叉树。 (a) 完全二叉树的 BFS 序列有什么特征？ (b) 具体怎么用 BFS 检测？ (c) 写出代码并测试。

七、练习答案

9.3.1

树的结构：

              A
            /   \
           B     C
          / \     \
         D   E     F
            / \
           G   H

逐层分析：

层序遍历结果：A B C D E F G H

注意第 2 层：B 的孩子是 D、E；C 的孩子只有 F（右边）。

BFS 的顺序保证了"先处理完 B 的所有孩子，再处理 C 的孩子" —— 所以是 D E F，而不是 D F E。

这就是队列 FIFO 的作用：B 比 C 先入队，所以 B 的孩子也比 C 的孩子先入队。

9.3.2

(a) queue.Count

(b) sum / size

完整代码：

static List<double> LevelAverages(TreeNode? root)
{
    var result = new List<double>();
    if (root == null) return result;

    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        int size = queue.Count;          // (a) 先记住这一层有多少个节点
        double sum = 0;
        for (int i = 0; i < size; i++)
        {
            var node = queue.Dequeue();
            sum += node.Value;
            if (node.Left != null) queue.Enqueue(node.Left);
            if (node.Right != null) queue.Enqueue(node.Right);
        }
        result.Add(sum / size);          // (b) 这一层的平均值
    }
    return result;
}

(a) 必须在循环【之前】取 queue.Count。

因为循环过程中队列会不断被加入下一层的节点 —— 如果在循环里读 queue.Count，它会一直变。

9.3.3

• (a) 错。 层序遍历用队列，不用栈。

  用栈的是 DFS。 栈的 LIFO 会导致"一条路走到底"，队列的 FIFO 才能保证"一层一层"。

• (b) 错。 完全看树的形状： | 树形 | BFS 空间 | DFS 空间 | |---|---|---| | 完全二叉树 | $O(n)$（最宽的一层） | $O(\log n)$ | | 退化链 | $O(1)$ | $O(n)$ | >

  宽而浅的树，DFS 省；窄而深的树，BFS 省。

• (c) 错（这是本节最值得澄清的一点）。

  两者的时间复杂度都是 $O(n)$ —— 最坏情况下都要访问所有节点。

  BFS 快是因为它"可以提前停止" —— 第一次遇到叶子就返回，不需要走完全程。

  实测：6 个节点的树上，BFS 只访问了 3 个就停了。

  "提前停止"是 BFS 在"求最短"类问题上的核心优势，而不是"复杂度更低"。

9.3.4

(a) BFS。

(b) 因为"最短关系链"就是"最少步数"。

• BFS 按"距离起点的步数"一层层扩散：第 1 层是直接朋友，第 2 层是朋友的朋友……
• 第一次到达目标时，走的一定是最少步数 ✓
• DFS 不行：它可能沿着一条很长的链钻下去，找到一个"走了 10 步"的路径，却错过了另一条"3 步就到"的路径。

这就是 12 章"无权图最短路径"的核心原理。

注意前提：每条边的"代价"必须相同（这里每条关系链都算一步）。

(c) 不能直接用 BFS 了。

因为"亲密度权重"让每条边的代价不同了。

BFS 的"第一次到达就是最短"依赖的是"每层之间步长相同"这个前提。一旦边的权重不同，"步数最少"就不等于"总权重最小"了。

这时候需要 Dijkstra 算法（13.3 节）：

Dijkstra 可以理解为"带权重的 BFS" —— 它不再用简单的队列，而是用一个优先队列（堆），每次取出"当前距离最小的节点"来扩展。

对比：

• BFS：用队列，按"步数"一层层扩展 → 适合无权图
• Dijkstra：用优先队列，按"累计权重"由小到大扩展 → 适合非负权图

BFS 是 Dijkstra 在所有边权重都为 1 时的特例。

9.3.5

(a) 完全二叉树的 BFS 序列特征：

把 BFS 序列写出来，所有的"空位"必须出现在最后 —— 也就是"一旦遇到空孩子，后面就不能再有非空节点"。

举例：

  完全二叉树:     1              BFS: 1, 2, 3, 4, 5, null, null
                /   \            展开成数组: [1, 2, 3, 4, 5, _, _]
               2     3           空位全在最后 ✓
              / \
             4   5

  非完全二叉树:   1              BFS: 1, 2, 3, null, 4
                /   \            展开成数组: [1, 2, 3, _, 4]
               2     3           中间有空位 ✗
                \
                 4

(b) 检测方法：

用 BFS 遍历，把空孩子也当成"节点"入队。
用一个标志 seenNull 记录「是否已经遇到过空节点」。

对队列里取出的每个节点：
  - 如果是 null：
        设置 seenNull = true
  - 如果不是 null：
        如果 seenNull 已经是 true  -> 说明"空位之后又出现了非空节点" -> 不是完全二叉树
        否则 -> 把它的左右孩子（可能是 null）都入队

遍历结束都没违反规则 -> 是完全二叉树

(c) 完整代码：

static bool IsCompleteTree(TreeNode? root)
{
    if (root == null) return true;

    var queue = new Queue<TreeNode?>();
    queue.Enqueue(root);
    bool seenNull = false;

    while (queue.Count > 0)
    {
        var node = queue.Dequeue();

        if (node == null)
        {
            seenNull = true;              // 遇到空位
        }
        else
        {
            if (seenNull) return false;   // 空位之后还有非空节点 -> 不完全
            queue.Enqueue(node.Left);     // 注意：null 也要入队！
            queue.Enqueue(node.Right);
        }
    }
    return true;
}

测试用例：

这个解法的妙处在于"把 null 也入队" —— 这样"空位"就成了 BFS 序列里的一个明确的元素，而不是"不存在"，从而能被检测到。

这是一种通用技巧：把"缺失"显式化，让它变得可检测。 在别的场景里也会用到（比如用哨兵节点把"空链表"变成普通情况，见 4.3 节）。

八、常见错误

九、本节总结

1. BFS 用队列，DFS 用栈 —— 容器决定了"一层层扩散"还是"一条路走到底"。
2. int levelSize = queue.Count; 是"按层分组"的关键 —— 必须在循环开始前取。
3. 实测层序：1 2 3 4 5 6 7（对比前序 1 2 4 5 3 6 7）。
4. 右视图：1 3 6 7 —— 用 i == levelSize - 1 只取每层最后一个。
5. BFS 求最小深度可以提前停止（实测 6 个节点的树只访问了 3 个），这是它在"求最短"类问题上的核心优势 —— 而不是"复杂度更低"。
6. "第一次到达就是最短"依赖"边权相同"。带权图要用 Dijkstra（13.3 节）。
7. BFS 和 DFS 的空间开销取决于树的形状 —— 宽树 DFS 省，深树 BFS 省。

下一节衔接：到这里，树的遍历方式都讲完了。但真正写树题时，难点往往不是"怎么遍历"，而是"递归函数该返回什么"。同一道题，返回值设计得好，代码五行；设计得不好，就要写一堆辅助函数。下一节讲一套通用的方法论。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "9.3",
  "title": "广度优先遍历与层序",
  "covered": [
    "BFS 的水波纹直觉与层序概念",
    "层序遍历实现与「为什么必须用队列」的分析",
    "按层分组的关键行 levelSize = queue.Count",
    "两种写法对比（levelSize vs 带层号入队）",
    "右视图应用（i == levelSize - 1 模式）",
    "最小深度：BFS 提前停止的实测（6 节点只访问 3 个）",
    "「BFS 优势是提前停止而非复杂度」的澄清",
    "BFS 与 DFS 的完整对比（含空间取决于树形）",
    "BFS 是最短路径的基础（12 章铺垫）与 Dijkstra 的关系"
  ],
  "unresolved": [
    "无权图最短路径留到 12.3",
    "Dijkstra 留到 13.3",
    "队列已在 5.2 节讲过，此处呼应"
  ],
  "canonical_terms": {
    "广度优先": "一层一层向外扩散的遍历策略",
    "层序遍历": "二叉树的 BFS，按层从上到下、每层从左到右",
    "BFS": "Breadth-First Search，广度优先搜索"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 9.2 的深度优先遍历与 5.2 的队列",
    "读者会使用 C# 的 Queue<T>"
  ],
  "word_count_actual": 2960,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch09/Sec93/",
    "层序/分组/右视图/最小深度对比均为实测",
    "练习 9.3.1 的层序推演已手工验算",
    "术语写法与 glossary.md 一致"
  ],
  "next": "9.4 树题递归套路：返回值该是什么"
}