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

以下代码实现了二叉树的广度优先搜索（BFS），并查找特定值的节点，则横线上应填写（ ）。

TreeNode* findNode(TreeNode* root, int target) {
    if (root == nullptr) return nullptr;

    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();

        if (current->val == target) {
            return current; // 找到目标节点
        }
        // 在此处填入代码
    }
    return nullptr; // 未找到目标节点
}

A.

if (current->left) q.push(current->left);
if (current->right) q.push(current->right);

B.

if (current->left) q.pop(current->left);
if (current->right) q.pop(current->right);

C.

if (current->left) q.front(current->left);
if (current->right) q.front(current->right);

D.

if (current->left) q.push(current->right);
if (current->right) q.push(current->left);

根据上下文和C++语法规则确定空缺处应填的内容，关注函数调用参数、表达式和返回值类型。

填空时注意语法完整性：分号、括号匹配、函数参数类型和个数、返回值类型。

【考点】二叉树遍历｜队列操作｜广度优先搜索

🎯 考纲定位 本题位于《GESP 六级数据结构和算法》模块，核心考查二叉树遍历与队列操作。命题人特意设计此题，就是卡住那些只背"BFS 用队列”却不懂"push 顺序决定层次遍历顺序”的考生，他们往往在左右子树入队时随意写，导致逻辑混乱。

🧠 解题思维 看到 BFS 框架，第一反应是"把左右孩子入队"。关键观察是：队列 FIFO 特性要求先入队的节点先被取出，若先 push 左孩子，则左子树会先被处理，这正是层次遍历的标准顺序。通法提炼：任何树的 BFS，都遵循"先 push 左孩子，再 push 右孩子"的模板，可迁移到多叉树、图的 BFS 等场景。

🪤 陷阱拆解 选项 B 把 push 写成 pop，利用了"队列 pop 是出队"的混淆，命题人故意用看似合理的 q.pop 来坑人；选项 C 用 q.front 返回前驱元素而非修改队列，属于 API 记忆错误；选项 D 左右顺序颠倒，虽然仍是 BFS，但层次遍历的规范顺序是先左后右，命题人用这个细节区分"懂顺序"和"只懂 BFS 概念"。如果你只背结论、不理解本质，就会掉进这些陷阱。

🔄 反命题思维 命题人视角：若把条件改成"先 push 右孩子"，答案会变成 D，即左右顺序决定遍历顺序，这就是同考点的变式。刷到类似题时，先问自己"命题人想考我什么"——是队列 API 还是遍历顺序？