开篇直入：二叉搜索树的“操作题”才是真正进入状态的地方
DAY20，第六章二叉树part07。训练营走到这里，二叉树已经从“遍历模板”正式转向“结构操作”了。前面你刷过了前中后序遍历、层序遍历、翻转、对称、路径总和、最大深度这些基础题，说实话那都是在树里“读取”信息，递归函数的思维还停留在遍历层面。而part07这五道题——二叉搜索树的最近公共祖先、插入操作、删除节点、修剪二叉树、有序数组转平衡二叉搜索树——一下子就变了：你要在树里“改写”结构，要维护二叉搜索树的顺序性质，要考虑删除一个节点之后怎么让整棵树依然是一棵合法的二叉树。
这部分的题目和前端、后端工程的关联非常直接。数据库索引、有序集合底层、路由表的组织、文件目录的查找，背后都是二叉搜索树的变形和升级。换句话说，二叉搜索树的操作能力，直接决定你能不能看懂后续的红黑树、AVL树、B+树。这篇博文我按训练营DAY20的节奏，把这批题的核心思路、代码细节、易错点完整拆开讲，也加入我当年实操时踩过的坑，想拿捏二叉搜索树这part的同学可以直接照着抄作业。
1. 先从整体思路说起：为什么这批题必须用递归
1.1 二叉搜索树的“左小右大”到底帮我们省了什么
二叉搜索树（Binary Search Tree，BST）最核心的性质就一句话：左子树所有节点的值都小于根节点，右子树所有节点的值都大于根节点。而且这个性质是递归定义的，每个子树自身也满足。
这个性质意味着什么？在普通二叉树上找一个节点，你没有任何“方向感”，只能在递归里把整棵树过一遍。但在二叉搜索树上，你对比当前节点的值和目标值，就可以直接决定往左走还是往右走——一次对比，砍掉一半的搜索空间。这个特征让复杂问题变得“有方向”。
以“二叉搜索树的最近公共祖先”为例。如果题目给的是一棵普通二叉树，找最近公共祖先的标准做法是：递归遍历左右子树，如果左右都找到了目标，那当前节点就是公共祖先；然后向上传递。但BST给的额外信息直接把这个问题的代码量砍掉一截：因为值有大小顺序，公共祖先必然在这个区间之内。
很多人在这一步会犯一个“经验主义错误”：觉得反正我有普通二叉树那套解法，凭什么要区别对待BST？确实，普通解法也能过，但性能差、代码长，更重要的是你浪费了一次训练思维的机会。BST的题本质是在逼你“把搜索区间收窄”这个意识刻进本能，后面的删除、修剪全是这个思路。
1.2 递归三步法在这个part里怎么套
代码随想录一直强调递归三步法：参数和返回值、终止条件、单层递归逻辑。DAY20的题目，每一道都是这个框架的实战演练。
这里我想给一个建议：不要机械地认为“递归返回值必须原样返回”。在删除节点和修剪BST这类题里，递归函数的返回值是“处理完的子树根节点”，上游得用这个返回值去更新链接。换句话说，很多人在删除节点那道题上卡住，不是逻辑不懂，而是返回值没接住。下面我会在实操部分把这块掰开揉碎。
还有一点，对于BST，单层递归逻辑里往往会基于当前节点的值和条件比较，决定是递归去左子树还是右子树，这跟普通二叉树那种“先递归左再递归右两块都走”的模式本质不同。把“二选一”和“左右都走”两种模式分清楚，这道题就通了一半。
1.3 为什么说part07是二叉树题型的分水岭
训练营前几天的题目，主要练遍历、路径类问题，递归基本上就是“遍历框架往里套逻辑”。你只要能记住前中后序的模板，很多题就是换汤不换药。
到了二叉树part07，一个是引入二叉搜索树这个特殊结构，另一个是引入了“结构修改”这个动作。删除节点、修剪，都要真的把树的结构改掉。这要求你对指针/引用、递归返回值、树节点之间的关系有清醒的认知——已经不是“读树”，而是“改树”了。
我自己的感受是，跨过这个分水岭之后，后续遇到二叉树的更多进阶题型，包括构造二叉树、二叉搜索树转累加树、平衡二叉树调整，你会自然觉得顺。所以DAY20值得你慢下来，这几道题值得反复写三遍以上。
2. 最近公共祖先：BST顺序性带来的“降维打击”
2.1 先给题目场景，和普通二叉树版本对比
题目是：在一棵BST中给定两个节点p和q，找到它们的最近公共祖先。公共祖先的定义是：一个节点，它同时是p和q的祖先，并且深度尽量深。
普通二叉树的场景里，没有顺序信息，只能往递归的“重叠判断”上去做：后序遍历，如果当前节点等于p或q，或者左、右子树分别找到了p和q，那当前节点就是答案。这种解法对任何二叉树都对，但你需要探索整棵树。
但在BST里，你手上有值的大小关系。比如p的值比根节点小、q的值比根节点大，那根节点是不是一定是公共祖先？你需要想一想蠢一点的答案：有可能，但也可能根节点的左子树里某个节点本身就是q的祖先。真正的最近公共祖先应该是在哪个位置？**如果在BST里，p和q一个在左子树、一个在右子树，那当前根节点就是唯一的分叉口，必然是最近公共祖先。**如果p和q都在左子树，最近公共祖先必然在左子树里，你的搜索方向也就唯一确定了。
2.2 递归写法的完整逻辑与代码
递归函数定义：给定当前节点cur、目标节点p和q，返回以cur为根的子树中p和q的最近公共祖先，如果p和q不在这个子树中，就返回null。
终止条件：
- cur为空，返回null。
- cur的值在p和q之间（包含等于），直接返回cur。
单层逻辑：
- 如果cur的值大于p和q的值，说明两个目标都在左子树，递归cur.left。
- 如果cur的值小于p和q的值，说明两个目标都在右子树，递归cur.right。
- 否则说明cur的值介于p和q之间，cur就是答案。
第三点为什么这里可以直接断定是答案？因为BST有序性：如果cur的值介于p和q之间，那么p和q必然分别位于cur的左右子树（或其一就是cur）。cur往下任何一层递归，必然无法同时包含p和q这两个分支，它已经是最深的那个“公共祖先”了。
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == NULL) return NULL; if (root->val > p->val && root->val > q->val) { TreeNode* left = lowestCommonAncestor(root->left, p, q); if (left != NULL) return left; } if (root->val < p->val && root->val < q->val) { TreeNode* right = lowestCommonAncestor(root->right, p, q); if (right != NULL) return right; } return root; }代码里那个if (left != NULL) return left;是不是有点冗余？其实这里因为BST的性质，只要进入左分支，答案一定在左子树里，不会返回NULL。但写上这个判断，能让代码更严谨：万一输入的数据有问题，也不会把空的回溯结果错误地当成答案。
2.3 迭代版本也很短，但为什么我推荐先写递归
BST顺序性的好处就是，这个题目迭代非常简单：
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { while (root != NULL) { if (root->val > p->val && root->val > q->val) { root = root->left; } else if (root->val < p->val && root->val < q->val) { root = root->right; } else { return root; } } return NULL; }有人可能会问，这么简单，为什么训练营还要求先写递归？原因是后续的插入、删除、修剪都要用递归返回值去更新结构，递归是主旋律。迭代能解决某个具体问题，但递归的“返回值承接”能力是这个part后面题目的核心能力。你可以写完递归之后，再顺手把迭代写一遍，体会两种写法的思维差异。
2.4 这个题目容易踩的几个坑
第一，忽略“等于”的情况。p和q里有一个可能就是当前节点本身，那最近公共祖先就是那个节点。所以判断的时候要用>=、<=或者单独判断相等，别只写严格大于和严格小于。
第二，误以为一定要遍历整棵树。很多初学者拿着普通二叉树的解法往上套，左右子树全都递归，最后也能过，但完全没有用到BST特性。面试时如果面试官问你“你能优化一下吗”，你就要能说出顺序性的利用。
第三，函数的返回类型和参数要一致。有的初学者写回溯的时候，返回的是布尔值，说是“找到了”，但外层又需要节点本身，于是临时改成传引用“存结果”，代码变得非常绕。其实就是直接把函数的返回类型定义成TreeNode*，然后利用“答案只出现在一条递归路径上”这个性质传递即可。
3. 插入与删除：BST结构维护的必修课
3.1 插入操作：为什么“沿着路径走到空位”就完事了
题目是给定BST和一个要插入的值，要求返回插入后的根节点，且插入后的树仍然是BST。
刚看到这题，很多人会想：BST插入是不是要旋转、调整、保证平衡？其实完全不用。BST的插入有一个非常自然的规律：对于任意一个空位，插在那里的新节点都不会破坏BST的有序性，因为那个位置本来就是根据大小关系“走到尽头”的位置。
插入的递归逻辑：
- 如果root为空，直接返回新节点。
- 如果val大于root的值，递归向root.right插入，并把返回值赋给root.right。
- 如果val小于root的值，递归向root.left插入，并把返回值赋给root.left。
注意，题目不要求平衡，所以这个操作的时间复杂度是O(h)，h是树高。极端情况下BST退化成链表，插入也是O(n)，这是后面平衡树解决的问题，在这个阶段你不需要研究怎么旋转。
TreeNode* insertIntoBST(TreeNode* root, int val) { if (root == NULL) { TreeNode* node = new TreeNode(val); return node; } if (val < root->val) { root->left = insertIntoBST(root->left, val); } else if (val > root->val) { root->right = insertIntoBST(root->right, val); } return root; }这里我要特别强调一个细节：必须把递归返回值赋给对应的子节点指针。root->left = insertIntoBST(root->left, val);这一行里的赋值是必须存在的，它保证新节点能真正挂到树里。如果你写成了直接调用insertIntoBST(root->left, val);而不用左指针接收，新节点就“丢了”，整棵树的根虽然没变，但左子树里什么都没发生。
这也是我刚开始刷这道题时长犯的错：觉得递归就是“递归函数内部改树”，忽略了返回值需要在上层被接住。BST的修改型递归，和之前的遍历型递归，最大的差别就在这里。
3.2 删除节点：五种情况逐一拆解
删除节点是part07里公认的难点。题目：给定一个BST的根节点和一个key，删除值为key的节点，并保持BST有序性。
递归函数的定义：以root为根的子树，删除key节点之后，返回新的子树根节点。
先定终止条件：root为空，直接返回NULL，因为删了个寂寞。
单层逻辑分种情况：
- root的值不等于key：根据key和root值的大小关系，决定往左还是往右递归，并把返回值赋给对应的子节点。
- root的值等于key：这时要根据root的孩子情况处理：
- root是叶子节点：直接返回NULL，把父节点中的链接置空。
- root只有右孩子：返回root->right，让右孩子顶替root的位置。
- root只有左孩子：返回root->left，让左孩子顶替。
- root既有左右孩子：用右子树里的最小值节点（左子树的最左节点）来替换root，同时删除那个最小值节点。
第4种情况最麻烦。为什么非得用右子树最小值来替换？因为BST的性质是左小右大。root被删除之后，要选一个节点来顶替root，这个节点必须大于左子树的所有值、小于右子树的所有值。右子树里的最小值恰好满足这个条件：它大于右子树中的所有最小值以下的节点？注意，右子树的最小值是右子树里最小，但它仍然大于root的值，而左子树所有节点都小于root的值，所以它一定大于左子树全部；同时它小于或等于右子树中其他节点，所以顶替root之后，右子树依然有序。同理，你也可以用左子树的最大值来替换。两者选一个即可，代码习惯上用右子树的最小值。
TreeNode* deleteNode(TreeNode* root, int key) { if (root == NULL) return NULL; if (root->val == key) { // 情况1：叶子 if (root->left == NULL && root->right == NULL) { delete root; return NULL; } // 情况2：只有左孩子 else if (root->left != NULL && root->right == NULL) { TreeNode* retNode = root->left; delete root; return retNode; } // 情况3：只有右孩子 else if (root->left == NULL && root->right != NULL) { TreeNode* retNode = root->right; delete root; return retNode; } // 情况4：左右都有孩子 else { TreeNode* minNode = root->right; while (minNode->left != NULL) { minNode = minNode->left; } root->val = minNode->val; // 删除右子树里这个最小节点 root->right = deleteNode(root->right, minNode->val); return root; } } if (key < root->val) { root->left = deleteNode(root->left, key); } else if (key > root->val) { root->right = deleteNode(root->right, key); } return root; }情况4里用root->val = minNode->val的方式，做了一个“值替换”，而不是真正把节点指针重新连接。这个写法简单、直观，也避免了处理minNode的父节点关系的复杂性。代价是什么？原来那个minNode节点的内存被拷贝了一个值，然后通过递归删除右子树里的那个节点。这个过程中，如果minNode本身既有右子节点，也只是一个“替换值+删除原节点”的过程，不会破坏结构。
3.3 删除两个孩子节点时的常见错误
我在实操中见到比较典型的问题有两个。
第一个问题是，在“只有左孩子”分支里，写成了root = root->left; return root;这种形式，没有先保存要返回的节点。C++里你还需要手动delete root来释放内存。如果忘了delete，内存就泄漏了。我在本地测试程序里跑了十万次删除操作，内存不释放会明显涨上去。刷题平台可能不校验这个，但工程上这是一定要做的。
第二个问题是，情况4里找到右子树最小值之后，直接把这个值赋给root，然后调用deleteNode(root->right, minNode->val)。这一步的返回值必须要赋给root->right。如果你不赋，那么“删除右子树里那个最小值”的操作，或者顶替上来的节点，不会真正更新到root的右孩子上，整棵树就断了一条链。
另外还有一个很隐蔽的坑：如果右子树的最小值节点就是root的右孩子本身，即右孩子没有左子树，那root->right = deleteNode(root->right, minNode->val)会把右孩子返回给root，这没问题。但如果右孩子有左子树，递归删除那个最左节点之后，返回值是你原来的右孩子（根不变），链接更新也没问题。但如果你在找最小值的时候直接记录了一个指针，并且想通过指针改父节点关系，那就容易写乱——所以直接用“值替换+递归删除”的写法更稳。
3.4 实操验证：删除操作做对了没？用中序遍历验证
BST有一个非常重要的性质：中序遍历结果是递增序列。所以每当你写完插入或删除操作之后，都可以用一个中序遍历来验证有序性。
我在本地练习的时候，会写一个工具函数：
void inorder(TreeNode* root) { if (root == NULL) return; inorder(root->left); std::cout << root->val << " "; inorder(root->right); }插入节点之后调用一次，输出应该是严格递增的。删除节点之后调用一次，输出仍然应该严格递增，且不再包含被删除的值。
这个方法实在太有用了。有时候你在删除逻辑里写错了一个链接，比如把返回值赋给了错误的方向，光看树的形状是看不出来的，但中序遍历序列一打印，马上就能看出哪个位置的值跳变。而且这个验证方式对你后续调试复杂逻辑也有效，早点把“中序有序”当成BST正确性的标尺焊在脑子里。
4. 修剪：区间约束下的BST结构调整
4.1 修剪问题的题目背景和暴力想法的陷阱
修剪问题描述：给定BST，和一个区间[low, high]，要修剪这棵树，使所有节点的值都在这个区间内，且保留原来树的相对结构。
举个例子：一棵BST里有值1、2、3、4、5，区间是[2, 4]，那么值为1和5的节点要删掉，剩下的树还得保持BST结构。
一个直白的暴力想法是：先把区间外的节点删除，用前面删除节点的逻辑一个个删。但这会非常麻烦：一个节点可能不在区间内，但它有子树，子树里的节点可能在区间内，你不能把它子树全部砍掉。
比如值小于low的节点，它的右子树里可能有值在区间内的节点，你只能剪掉这个根节点，但要把它的右子树保留下来（并在右子树里继续修剪）。这个“保留一部分子树”的思维，是修剪题的核心难点。
4.2 递归返回值式修剪的完整思路
修剪递归函数定义：给定一个子树的根root，返回修剪后这棵子树的新根。
终止条件：root为空，返回NULL。
单层逻辑：
- 如果root的值小于low：root本身以及root的左子树全部要剪掉（因为左子树里所有值都比root小，更不可能满足下限）。但root的右子树中可能有满足条件的节点，所以返回修剪后的右子树，即
trimBST(root->right, low, high)。 - 如果root的值大于high：root本身和root的右子树全部要剪掉。但左子树里可能有满足条件的节点，返回修剪后的左子树，即
trimBST(root->left, low, high)。 - 如果root的值在区间内：root保留，然后递归修剪左右子树，并把修剪后的结果分别赋给root.left和root.right。
TreeNode* trimBST(TreeNode* root, int low, int high) { if (root == NULL) return NULL; if (root->val < low) { return trimBST(root->right, low, high); } if (root->val > high) { return trimBST(root->left, low, high); } root->left = trimBST(root->left, low, high); root->right = trimBST(root->right, low, high); return root; }这代码看起来短，但逻辑密度很高。我经常建议学员把这题的代码背诵下来，不是为了应试，而是因为“删根但保留子树”的return模式，在很多高级二叉树问题里都是一模一样的套路。
4.3 修剪过程中容易忽略的问题
修剪代码里，很多初学者容易在“root值小于low”的情况下直接return root->right，但忘了这个右子树里面可能还有大量的值小于low的节点。实际上你直接返回root->right，返回的右子树是“未修剪的”，里面可能还有很多区间外的节点。正确做法是递归去修剪右子树，再返回修剪结果。这个细节和插入、删除里的“返回值接住”一脉相承，本质都是递归函数必须处理子问题后再向上返回。
另一个值得注意的地方是：如果root在区间内，左右子树的修剪结果必须赋值回给root的左右指针。即使修剪后左右子树为空，也要把这个空值写进去，否则原来悬着的节点虽然没用了，但仍然挂在树上，遍历时会出问题。
这个题的时间复杂度是O(n)，因为每个节点最多被访问一次，空间复杂度是O(h)。因为BST的顺序性，我们其实可以通过比较节点值来提前剪枝，但实际上即使一路访问到最后，每个节点也只访问一次。
4.4 从修剪看“递归返回新树根”的通用模式
到这里你应该发现一个规律：插入、删除、修剪，三个操作，递归函数的整体框架高度一致——“根据条件决定往左递归还是往右递归，然后用返回值更新子指针”。区别只在于“当前节点自身怎么处理”。
这个模式可以很好地迁移到很多BST问题上：BST的最近公共祖先、BST的搜索、甚至BST转累加树。当你把“递归返回更新后的子树根”当成一种条件反射，后面看AVL、红黑树的旋转操作会顺着很多，因为你已经习惯了“递归函数的返回值就是处理后子树的根节点”。
我在实际刷题时体会是，这个阶段不要贪多，每天把这几个模式写三遍，写到不假思索，效果比你刷十道新题好得多。
5. 常见问题与排查技巧实录
5.1 递归返回值丢失，树上什么都没变
这是我和学员讨论时出现频率最高的问题。插入操作里，写了insertIntoBST(root->left, val);却没接收返回值，结果是函数进入左子树后创建了新节点，但因为返回值没有被赋值给root->left，新节点和树之间没有建立连接。运行起来程序不报错，中序遍历一看，值根本没插进去。
排查办法非常简单：在中序遍历结果里查找输入的值，如果没找到，先别怀疑键盘录入，先检查递归返回值有没有被接住。写代码的时候，看到“递归调用一个返回TreeNode*的函数”，第一反应就是这一句调用是不是被赋给了某个指针。
5.2 删除节点时只处理了值替换，忘了释放内存和更新链接
我在删除两个孩子节点的情况里，最初只写了root->val = minNode->val;然后没有调用递归删除右子树里的那个最小值节点。当然这样中序遍历没有重复值，看起来也对，但你仔细检查会发现，原来的minNode节点还在树上，它和root现在的值重复了。这就是典型的“逻辑上删了，结构上没删”。必须调用deleteNode(root->right, minNode->val)把那个节点从树上彻底摘掉。
另外在“叶子节点”情况下，用C++写的同学记得先delete root再return NULL。刷题平台如果不查内存泄漏可能无所谓，但面试官可能会追问“你怎么处理内存释放”，以及当你在一个长期运行的程序里反复操作BST，内存泄漏会导致进程内存持续上涨。
5.3 递归深度和极端数据：退化链的风险
BST在普通输入下，树高约为O(logn)。但如果数据是“有序插入”的，比如你依次插入1、2、3、4、5，BST就会退化成一条链，此时树高为O(n)。递归深度会达到n，在数据量大的时候，可能直接爆栈。
我在本地测试时构造了一个10万个节点的有序插入序列，然后执行删除操作，程序直接在递归入口崩溃。实测下来，在默认栈空间大小下，递归深度超过数万层就会有问题。所以你在练习的时候可以选择递归写法，但要心里清楚：这种写法在工程上存在栈溢出风险。
如果要更稳妥，可以尝试把删除操作改写为迭代版本，但迭代版本删除节点的代码很容易出错，尤其处理两个孩子的替换节点时，需要对父节点做不同的分支判断。我的建议是：先掌握递归版本，再挑战迭代版本。训练营的核心目的是理清原理，不是让你一上来就写最优工程代码。
5.4 一个综合自测题：删除+修剪的交叉验证
修剪和删除容易搞混，但它们的本质区别其实一句话：删除是删一个点，修剪是按区间删一批点。我给自己设置的一个自测题是：给定一棵BST，先往里面插入一堆值，然后用修剪函数把区间过滤一遍，再手动随机删除几个节点，每步都打印中序遍历序列。
如果所有步骤输出都是有序的，那么这批量操作基本就稳了。如果再配合打印树的层数、节点数量，你可以大致判断结构有没有被破坏。实测下来，这套自测流程帮我发现了很多“输出有序但是链接错误”的隐蔽bug，比单纯对拍标准答案更能提升手感。
5.5 刷到这里的几条私人心得
第一，BST的题目先画图再写代码。我在本子上面画一棵BST，手动模拟删除一个有两个孩子的节点，画了几遍之后，情况4的思路自己就出来了。只靠脑内模拟很容易漏情况。
第二，每道题写完之后，追问一句“如果输入很多重复值怎么办”。BST允许节点值重复时，插入、删除的逻辑会有变化。训练营的题目默认不包含重复值，但培养边界意识很重要。实际上，工程中如果需要允许重复，通常会用“每个节点存一个计数器”或者“左子树小于等于根、右子树大于根”的约定，后续在业务代码中很常见。
第三，刷题不要只看题解，要能自己讲出来。我每次复习part07的时候，都会把五个题的思路对着模拟面试的方式说一遍：参数定义是什么，返回值怎么接，哪种情况返回自己、哪种情况返回子树。能流畅讲出来，才代表这块真的变成你的了。
DAY20这部分内容量不小，但含金量很高。你在这个part里形成的“递归返回值+子指针更新”的肌肉记忆，会在后续几乎所有二叉树结构操作的题目里反复用到。如果你现在写得慢、容易错，都正常——我当时也是反复推到重来好几轮才完全搞清楚。慢一点，把每种情况亲手画一遍、写一遍、验证一遍，这一关过了，二叉树的后半程你会明显轻松。
