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

以下代码实现了二叉排序树的哪种操作？

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

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

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

【考点】

二叉搜索树插入｜递归修改树结构｜返回值语义

🎯 考纲定位

GESP 六级 数据结构与算法模块，二叉树操作章节。命题人专门卡住"树修改类操作"的识别能力——学生容易把插入误看成查找，因为两者都走 BST 路径，但插入必须创建新节点并返回修改后的子树根，这个双重签名（new+TreeNode*返回）是六级区分度所在。

🧠 解题思维

看到递归函数名 op 和返回值类型 TreeNode*，立刻联想到是修改树结构的操作。递归终止条件 root==nullptr 时返回 new TreeNode(val)，这是插入空子树的标志。递归调用 op(root->left,val) 后会更新 root->left 指针，说明在调整指针结构。二叉树插入通法：递归定位到空位，创建新节点，回溯更新指针。

🪤 陷阱拆解

A 查找：通常返回 bool 或 TreeNode*，但绝不会创建新节点。C 删除：涉及查找后继/前驱，递归返回后通常不创建节点。D 遍历：是访问而非修改。最阴险的是返回值类型 TreeNode*——如果只背"插入就是往左右走"的结论，会忽略这个签名，误判成查找。

🔄 反命题思维

把 new TreeNode(val) 改成 return nullptr;，变成什么题？这是考察查找操作，因为查找成功返回节点指针，失败返回空。刷到类似题，先问自己"返回值类型是什么？函数体是否创建新节点？"