GESP 六级 · GESP 202409 C++ 六级 第 11 题

上一题的二叉树深度计算还可以采用二叉树的广度优先搜索来实现。以下基于二叉树的广度优先搜索实现的深度计算函数中横线上应填写（ ）。

#include <queue>

int max_depth_bfs(tree_node* root) {
    if (root == nullptr) {
        return 0; // 如果树为空，深度为 0
    }

    queue <tree_node*> q;
    q.push(root);
    int depth = 0;

    // 使用队列进行层序遍历
    while (!q.empty()) {
        ________________________  // 在此处填入代码
        for (int i = 0; i < level_size; ++i) {
            tree_node* node = q.front();
            q.pop();

            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
    }

    return depth;
}

排列组合问题：先判断是否考虑顺序（排列P vs 组合C），再确定是否允许重复。乘法原理分步，加法原理分类。

区分排列（考虑顺序，$P(n,m)$）和组合（不考虑顺序，$C(n,m)$）。注意特殊元素优先处理、正难则反等计数技巧。

【考点】广度优先搜索｜二叉树层级遍历

GESP 六级《数据结构与算法》模块，考点为二叉树的广度优先搜索与层级遍历。命题人为什么在试卷里放这道题——它卡住了绝大多数考生对 BFS 队列状态管理的理解。

看到题先想 BFS 的层序遍历核心：队列里存的是当前层节点，遍历完一层后 depth+1。关键观察是 while 循环里必须先记录 q.size() 代表当前层节点数，再逐层出队，否则 depth 会错位。每一步推理依据是队列先进先出和树的层级特性。通法：所有 BFS 层数统计题，都是 int level = q.size(); 然后循环 level 次，每次 depth++。这类题的通用模板就是先记录当前队列大小再内层循环。

选项 B、D 把 level_size 硬编码为 2，命题人利用考生对完全二叉树的惯性思维；选项 C 把 depth+=level_size，偷换概念成“累加节点数”而非“层数”。最阴险的是空白后没有再改 depth，如果你只背"BFS 要 depth++"却忘了位置，就会选 C。如果你只背结论、不理解本质，就会掉进这个陷阱。

如果把深度改成“最大节点数”，那就要把 depth+=level_size，但题目问深度，所以必须 depth++。答案会怎么变？刷到类似题先问：命题人想考的是“层数计数”还是“节点计数”？