GESP 六级 · GESP 202512 C++ 六级 第 12 题

给定一棵普通二叉树（节点值没有大小规律），下面代码判断是否存在值为 $x$ 的结点，则横线处应填入（ ）。

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

TreeNode* bfsFind(TreeNode* root, int x) {
    if (!root) return nullptr;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode* cur = q.front(); q.pop();
        if (cur->val == x) return cur;
        __________________
    }
    return nullptr;
}

A. q.push(cur);

B. if (cur->right) q.push(cur->right);

C.

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

D.

q.push(cur->left);
q.push(cur->right);

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

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

【考点】广度优先搜索｜队列操作｜空指针判断

考纲定位：GESP六级树形结构专项，命题人把这道题放在这里就是卡住那些只会背BFS模板、却不懂"先判断后入队"的学生。六级树形题向来偏爱考察边界处理，这道题就是典型的"考察你是否真的懂队列"。

解题思维：看到BFS框架先反应过来——广度优先搜索的核心是逐层扩展，二叉树必须把左右孩子都加入队列。代码里cur已经出队，接下来就该把它的左右子节点塞进q。但这里有个细节：cur->left和cur->right都可能为nullptr，直接q.push(cur->left)会把空指针扔进队列，下一轮q.front()取出来就是nullptr，再访问cur->left就崩了。所以正确做法是先判断if (cur->left)，再q.push(cur->left)，同理处理右孩子。

陷阱拆解：逐个拆错项——A选项q.push(cur)是把当前节点又扔回队列，这会让队列无限膨胀，永远遍历不完；B选项只判断右孩子，左孩子被漏掉，搜索不完整；D选项最阴险，它没做if判断，直接把cur->left和cur->right扔进队列——如果某个子节点是nullptr，队列里就会混入空指针，下一轮q.front()取出来就是nullptr，再访问cur->left就崩了。这道题的陷阱就在于"推入队列前必须确认节点存在"，这是BFS实现里的铁律。

反命题思维：如果把这棵树改成完全二叉树，cur->left和cur->right就永远不会是空，那C选项里的if判断就可以省掉，直接q.push(cur->left); q.push(cur->right);也行。但命题人偏偏选了普通二叉树，就是要逼你写if判断。刷到类似题先问自己：这棵树是不是保证每个节点都有左右孩子？没有的话，就必须先判空再入队。