GESP 六级 第 06 讲：宽度优先搜索 BFS

本讲定位：单选第 12 题固定考「层序遍历的变体填空」——2026 年 6 月和 2026 年 3 月连续两次都是二叉树的右视图，2025 年 12 月是「普通二叉树里 BFS 找值」。加上单选第 6 题（用 BFS 判完全二叉树，六级第 03 讲已讲）和 1～2 道判断题，本讲覆盖 6～8 分。

BFS 和上一讲的 DFS 是一对：DFS 用栈往深处钻，BFS 用队列一层一层扫。六级第 01 讲的队列、六级第 02 讲的层序遍历，在这一讲合流成一个通用模板。

对应官方大纲：六级知识块 3「搜索算法」——宽度优先搜索算法（BFS）、二叉树的搜索算法。

前置知识：六级第 01 讲（队列）、六级第 02 讲（层序遍历）、六级第 05 讲（DFS）。

代码说明：本讲代码均已用 g++ 11.5（-std=c++11）编译运行验证；右视图程序与「DFS 先右后左记录每层首次到达」的独立实现对拍 500 组随机树。

1. BFS 是什么

$$ \boxed{\textbf{先把身边的都看一遍，再往外扩一圈；一层一层地扫}} $$

和 DFS 的对照——这张表要背：

DFS BFS
策略 一条路走到底 一层一层往外扩
容器 栈（或递归） 队列
访问顺序 深度优先 由近及远
空间 $O(树高)$ $O(最宽一层的结点数)$
擅长 子树统计、枚举所有方案 最短路（步数最少）、按层处理

⚠️⚠️ 判断题头号考点（2025 年 12 月六级判断第 4 题，官方答案「错」）：「广度优先遍历二叉树可用栈来实现」——不能。

理由：BFS 要求「先发现的先处理」，这正是队列的行为。换成栈就变成「后发现的先处理」，遍历顺序会退化成深度优先的样子。

反过来 DFS 可以用栈（六级第 02 讲第 3.4 节写过）。口诀：BFS 只能用队列，DFS 栈和递归都行。

2. 层序遍历模板 ★

六级第 02 讲写过基础版，这里把带层号的通用模板固定下来。本讲所有变体都是在这个模板里改一行。

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 建一棵固定的测试树，后面反复用
//              1
//           ┌──┴──┐
//           2     3
//         ┌─┴─┐    └─┐
//         4   5      6
//            ┌┘
//            7
TreeNode* buildDemo() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);
    root->left->right->left = new TreeNode(7);
    return root;
}

void levelOrder(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    int level = 0;
    while (!q.empty()) {
        int sz = q.size();                  // ★★ 必须先量长度
        level++;
        cout << "第 " << level << " 层: ";
        for (int i = 0; i < sz; ++i) {      // 这一层恰好 sz 个
            TreeNode* cur = q.front();
            q.pop();
            cout << cur->val << " ";
            if (cur->left)  q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
        cout << endl;
    }
}

int main() {
    levelOrder(buildDemo());
    return 0;
}

输出：

层 结点
第 1 层 1
第 2 层 2 3
第 3 层 4 5 6
第 4 层 7

（实测验证 ✅）

2.1 ⚠️ 为什么必须先 int sz = q.size();

2026 年 6 月六级判断第 8 题（官方答案「错」） 给的就是下面这个写法：

while (!q.empty()) {
    for (int i = 0; i < q.size(); ++i) {   // ← 错在这里
        TreeNode* cur = q.front();
        q.pop();
        cout << cur->val << " ";
        if (cur->left)  q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
    cout << endl;
}

问题出在：循环体里既 pop 又 push，q.size() 一直在变，而 i < q.size() 每一轮都要重新求值，于是「这一层有几个」的边界就完全失控了。

用上面那棵测试树实测，两个版本的对比：