GESP 六级 · GESP202609 C++ 六级 第 10 题

下面函数在二叉搜索树中查找值 x 。横线处应填写（　　）。

TreeNode *searchBST(TreeNode *root, int x) {
if (root == nullptr || root->val == x)
return root;
if (x < root->val)
return searchBST(root->left, x);
return __________________________;
}

BST 查找的核心是"左小右大"性质。看到题先想：当前节点值与目标值比较，小于则去左子树，大于则去右子树。题目已处理 x < root->val 的情况，横线处必须处理 x > root->val 的情况。递归调用时保持参数结构一致：传入子树根节点和原目标值。

A 选项是典型的方向混淆陷阱——把 x > root->val 误判为去左子树；C 选项偷换概念，修改目标值完全违背 BST 定义；D 选项看似简洁，但忽略了递归查找的返回值类型——若右子树为空，直接返回 root->right 会得到 nullptr，但题目要求的是"查找值 x"，若 x 不在右子树中，应继续递归，而不是直接返回右子树指针。

1. 考纲定位

本题考查 GESP 六级《数据结构与算法》模块中的二叉搜索树（BST）查找操作。命题人卡住的是学生是否真正理解 BST 的"左小右大"性质，而非死记硬背代码。六级难度要求能独立分析递归逻辑，这道题就是专门测试"比较后选择子树方向"这一核心能力。

2. 解题思维

看到题先想：BST 中，若 x < root->val，目标一定在左子树；若 x > root->val，目标一定在右子树。题目已处理 x < root->val 的情况，横线处必须处理 x > root->val 的情况。

关键观察：递归调用时保持参数结构一致——传入子树根节点和原目标值。

数值推演：假设 root->val = 10，x = 15。15 > 10，应进入右子树。若选 A（左子树），会错过 15；若选 D（直接返回右子树），若右子树为空则返回 nullptr，但若右子树存在且包含 15，则 searchBST(root->right, x) 才能递归查找。

通法：BST 查找的递归模板是 if (x < node->val) return searchBST(node->left, x); else return searchBST(node->right, x);。