GESP 六级 · GESP 202606 C++ 六级 第 13 题

下面代码实现二叉搜索树的插入操作。假设树中不存在重复值，横线处应填写（ ）。

TreeNode* insertNode(TreeNode* root, int x) {
    if (root == nullptr) {
        return new TreeNode(x);
    }
    if (x < root->val) {
        __________________________
    } else {
        root->right = insertNode(root->right, x);
    }
    return root;
}

根据二叉树的遍历特性，先/前序遍历确定根节点，中序遍历确定左右子树范围，从而重构整棵树，再输出后序遍历结果。

易混淆三种遍历的顺序。先序：根左右；中序：左根右；后序：左右根。注意遍历结果中相邻节点的关系。

【考点】递归｜二叉搜索树｜指针赋值

🎯 考纲定位 GESP 六级「数据结构与算法」模块核心考点。命题人专盯"指针引用传递易错点"，六级考生往往能写递归却栽在"返回值赋给谁"上，这是区分五级和六级的分水岭。

🧠 解题思维 递归插入的本质是：插入操作返回"新子树的根"。x 小于当前节点，说明要去左子树递归，得到的返回值就是更新后的左子树根，必须赋回给root->left。注意：root 是形参拷贝，递归返回时树结构已变，但函数外部的指针不变，所以 root = ... 只修改局部变量。

🪤 陷阱拆解 B 项让很多人选错——它修改了形参 root，但不会影响调用者的原指针。C 项方向全反。D 项看似调了函数，却丢了返回值，相当于白递归一遍。命题人用这个"无副作用调用"测试你是否真正理解指针与返回值的关系。

🔄 反命题思维 若把函数改为"返回新节点"（非递归树），横线就变成return insertNode(root->left, x);；若改成非递归写法，就没有这个递归调用的问题。刷到类似题先问：这个函数修改了谁？返回了什么？