代码随想录刷题——二叉树篇十五二叉树这一章刷到第十五篇基本就到二叉搜索树BST的增删节点环节了。很多人在这个位置卡住不是因为递归不会写而是因为BST的插入、删除操作不像普通二叉树那样“无脑递归”每一步都得维护“左小右大”的结构特性。尤其是删除节点要考虑的情况一下子从“一种”变成“五种”指针怎么指、返回值怎么接、父节点怎么连稍不留神就是空指针异常或者树结构被破坏。这篇内容就是围绕BST的插入和删除展开的重点解决两个问题第一为什么递归一定要用返回值接住新子树第二删除节点时左右孩子都存在到底怎么处理才能不破坏BST性质。适合正在刷代码随想录二叉树篇、卡在第十五篇附近或者想系统整理BST增删操作的读者。看完之后你可以直接照着里面的代码模板写题也能理解每一步背后的指针逻辑而不是死记硬背。1. 为什么BST的增删和普通二叉树不是一个难度先明确一个前提BST的价值在于“中序遍历有序”这个性质。往这个树里插一个节点、删一个节点不只是让树还存在还要让中序遍历结果依然有序。普通二叉树删除叶子节点直接置空就完事了但BST不行因为删掉的节点如果还有子树子树里的值必须找到合法的新位置否则整棵树就“失序”了。这里我要先纠正一个常见误区很多人在刷到BST增删时第一反应是“用平衡树的旋转”或者“先用中序遍历把树转成数组改完再建树”。这两种思路都能让结果正确但放在代码随想录这一系列里是跑偏的。旋转是AVL树和红黑树里的操作普通BST增删不需要旋转转数组再重建虽然简单但违背了“原地修改树结构”的刷题本意而且面试官一问删除的原地过程直接就露馅了。所以这一篇的所有解法都围绕一个核心思路递归函数的返回值就是“处理完这一棵子树之后新的子树根节点”。父节点只需要做一件事——把自己的左指针或右指针接住这个返回值。这样设计的好处是完全不需要维护父节点的指针递归天然帮我们把父子关系“传递”下去了。如果你之前刷过链表章节会发现这有点像删除链表节点的经典问题不使用虚拟头节点时必须记录prev指针。BST比链表更麻烦因为每个节点有两个孩子、两个分支而且删除后可能不止“跳过当前节点”这么简单。用“返回值接住新子树”这个模式正是为了解决多分支场景下父子关系难以维护的痛点。举一个具体的例子说明这个设计多么重要。假设我们要删除节点值为5的节点而它的右子树里有一堆节点如果不用返回值接住新子树删除完5之后父节点原本指向5的指针就变成悬空指针了。但用返回值整个过程是递归走到5时函数返回“删除之后的子树根”上层父节点立刻用返回值覆盖自己指向5的指针。指针更新在递归回溯的瞬间自然完成不需要提前记录任何额外信息。2. 插入节点两种写法的取舍与指针细节BST插入的逻辑比删除简单得多但它本身也有一个容易踩坑的点递归返回值到底要不要接。很多人想当然地写void insert(TreeNode* cur, int val) { if (cur nullptr) { cur new TreeNode(val); return; } if (val cur-val) insert(cur-left, val); else insert(cur-right, val); }这段代码跑起来新节点确实创建了但树里根本找不到它。原因在于C里cur是形参cur new TreeNode(val)只是让形参指向新节点函数结束后这个指针就丢了树本身没有任何变化。这就是典型的“指针作为参数但没有通过返回值或引用传回”的坑。2.1 递归插入的返回值设计代码随想录里推荐的写法是让插入函数返回节点指针用法如下TreeNode* insertIntoBST(TreeNode* root, int val) { if (root nullptr) return new TreeNode(val); if (val root-val) root-left insertIntoBST(root-left, val); else root-right insertIntoBST(root-right, val); return root; }这里最关键的一行是root-left insertIntoBST(root-left, val);赋值不是可有可无的。它把“插入后新子树的根”重新绑定到当前节点的左指针上。如果root-left原本是空那返回值就是新节点等于替当前节点挂上了这个新孩子如果root-left本身有内容返回值经过一路回溯仍然是原来的根相当于“什么都没变但走了一遍确认路径”。有些人会问“如果插入后子树根没变这步赋值不是浪费吗”确实在多数情况下返回值就是原来的根赋值不影响结果。但你不能不写因为“多数情况下没变化”和“一定没变化”是两回事。递归走到空节点时新节点是凭空出现的这棵新子树必须被接回上层结构。这就是为什么返回值必须被接住——虽然99%的递归分支是“原样返回”但存在新节点的那条分支返回值是有意义的。2.2 迭代插入与递归插入的对比迭代插入的思路也值得掌握因为很多编译器题目比如某些C刷题网站甚至更偏好迭代。核心逻辑是从根节点出发用parent记住当前节点的父节点一路往下走直到空位置然后判断新节点挂在左边还是右边。TreeNode* insertIntoBST(TreeNode* root, int val) { if (root nullptr) return new TreeNode(val); TreeNode* cur root; TreeNode* parent nullptr; while (cur ! nullptr) { parent cur; if (val cur-val) cur cur-left; else cur cur-right; } if (val parent-val) parent-left new TreeNode(val); else parent-right new TreeNode(val); return root; }这段代码虽然能通过所有测试用例但我个人不太建议在面试时优先写它。原因不是它错而是它把“父子关系”的管理从递归中剥离出来变成了显式的parent变量逻辑复杂度一下子起来了。万一树很大、你要在循环里做别的操作忘记更新parent就是经典Bug。相比之下递归版本只改两个地方思路非常统一。不过迭代版本的思路也有价值它让我真正理解了BST插入的本质插入一个新节点永远发生在“某个空指针位置”这个位置由节点的值大小一路比较决定而插入过程本身不会改变树中任何既有节点的值或结构。想通这一点你就能理解“为什么插入永远新增叶子节点”这件事不是规则限制而是BST性质本身就决定了新节点只能落在空位。3. 删除节点五种情况的完整拆解删除是BST章节里最容易让人崩溃的操作代码随想录里的做法是把情况分成五种我强烈建议你在纸上先把这五种情况画出来再去看代码。画一次图的效果大于刷十道题。3.1 情况分类与核心思路假设cur是当前访问到的节点key是要删的值完整的删除情况如下第一种没找到key返回原节点。第二种cur是叶子节点左右都为空直接删除返回空指针。第三种cur的左孩子不为空右孩子为空直接让左孩子顶替cur的位置。第四种cur的右孩子不为空左孩子为空直接让右孩子顶替cur的位置。第五种左右孩子都不为空这是最麻烦的需要把cur左子树整体挪到cur右子树中最左侧节点的左下方然后让cur的右孩子顶替cur。为什么分这么细因为删除一个节点的本质是“让某棵子树来接替被删节点的位置”。接替者不同处理方式就不同。叶子节点没有子树接替者就是nullptr只有一个孩子接替者就是那个孩子两个孩子都在接替者必须保证“它带着整棵子树一起移动后BST性质仍然成立”。这五种情况里前四种的代码几乎都是一两行的指针赋值问题// 第三种左不空右空 if (cur-left cur-right nullptr) return cur-left; // 第四种右不空左空 if (cur-right cur-left nullptr) return cur-right;难点永远在第五种。我见过很多人在第五种这里写“找到右子树的最小节点把它的值赋给cur然后递归删除那个最小节点”。这种思路叫“值替换法”代码上也很标准但我强烈建议你先掌握代码随想录里的“左子树嫁接到右子树最左”的思路因为它更直观也更能训练你对BST结构本身的理解。3.2 左右子树都在时的两种处理方案方案一左子树嫁接到右子树最左节点。右子树的最左节点是右子树中值最小的节点。由于被删节点的左子树里所有值都小于右子树中的任何一个值所以把整个左子树挂到右子树最左节点的左边只会得到一个更小的值位于右子树最左侧依然满足BST性质。挂接完成后被删节点的右子树成为新的子树根返回它。if (cur-left cur-right) { TreeNode* node cur-right; while (node-left ! nullptr) node node-left; node-left cur-left; return cur-right; }这里while (node-left ! nullptr)一直在右子树里往左走直到走到最左端。这一步必须走到“最后”而不能只走一步因为右子树的最左节点可能藏得很深。举个例子右子树的根没有左孩子那node就是右子树根左子树直接挂到右子树根左侧没问题但右子树的根有左孩子、左孩子又有左孩子时就必须一路走到最底层否则挂在中间节点左边会把后面的左孩子覆盖掉。方案二值替换法。找到右子树最小节点把它的值赋给当前节点再递归删除那个最小节点。这个过程本质上是在“换一个节点来当这个位置的主人”删除操作就转移到了右子树最小节点那里去了。if (cur-left cur-right) { TreeNode* node cur-right; while (node-left ! nullptr) node node-left; cur-val node-val; cur-right deleteNode(cur-right, node-val); }这两种方案都能AC但有一个细节很多人忽略了值替换法在二叉搜索树中其实是安全的但在某些扩展题目里你需要保留节点的其他附加信息比如以该节点为根的子树节点数直接覆盖值就会丢失这些附加信息。所以如果你后续打算做更进阶的树结构题目建议先吃透方案一的“指针搬运”思路不会丢失任何附加信息。3.3 完整代码模板与逐步走读把五种情况串起来完整删除代码是这样的TreeNode* deleteNode(TreeNode* root, int key) { if (root nullptr) return nullptr; if (key root-val) { root-left deleteNode(root-left, key); } else if (key root-val) { root-right deleteNode(root-right, key); } else { // 找到要删的节点了分情况处理 if (root-left nullptr root-right nullptr) { return nullptr; } else if (root-left ! nullptr root-right nullptr) { return root-left; } else if (root-left nullptr root-right ! nullptr) { return root-right; } else { TreeNode* node root-right; while (node-left ! nullptr) node node-left; node-left root-left; return root-right; } } return root; }逐步走读一遍假设树是这样5 / \ 3 6 / \ \ 2 4 7现在删除3。递归走到5因为3 5所以root-left deleteNode(root-left, 3)。进入3节点发现key 3开始处理。3的左右孩子都存在进入第五种情况node先指向3的右子树根44没有左孩子所以node-left 3的左子树2此时3的右子树4成为新子树根返回4。回到上一层5的左指针接住4树变成5 / \ 4 6 / \ 2 7可以看到2原本在3的左边现在挂在4的左边BST性质完全成立。而且这种操作没有改变任何节点的顺序关系只是物理位置变化了。有一种常见的误解这个操作会让树高度增加变“歪”。确实如果被删节点左子树很大、右子树很小嫁接后整体可能更倾斜。但这是普通BST的固有特性不是这里处理方式的问题。如果你担心树的平衡性后面学AVL或红黑树时自然会用到旋转来平衡高度。刷BST增删时核心目标是“结构和顺序都对”。4. 容易被忽略的边界条件与排查实录刷题最痛苦的不是不会写而是写了半天提交报错报在你想不到的地方。BST增删看似简单边界条件却极其隐蔽。我把实际刷题中遇到过的典型问题整理成一份速查这些坑代码随想录里没有专门列出来但只要你写过一遍绝对会碰上。4.1 递归返回值丢失问题最经典的问题是递归函数正确返回了新子树根但调用处没有接住返回值。对比这两段代码第一段能过第二段不能过// 对的 root-left deleteNode(root-left, key); // 错的 deleteNode(root-left, key);区别在于第二段把删除后的结果丢弃了。如果删除发生在叶子节点被删节点的父节点指针依然指向已释放的内存访问时就会得到未知结果。这个坑我在自己写代码时踩过好几次尤其容易发生在“递归路径比较长”的情况下因为你会觉得“反正递归过程中已经改了指针”实际上递归函数内部的指针改动如果不通过返回值传回上层上层根本感知不到。排查方法很简单每次调用递归函数后检查你是否把返回值赋给了对应的left或right字段。这个习惯要在前期就养成因为后续刷“修剪二叉搜索树”“二叉树的最近公共祖先”时到处都是这种“返回值接住新子树”的模式。4.2 空指针与根节点删除删除根节点是另一个高频出错点。很多人写删除时会假设“根节点一定有个父节点”然后试图维护parent指针。实际上删除操作必须能独立处理“删除的是根节点”这种情况。在代码随想录删除模板里这其实是自动解决的当key root-val时返回值是新的根节点如果根节点是叶子返回nullptr如果根节点只有一个孩子返回那个孩子如果左右都在返回右子树。整个过程不依赖任何父节点信息所以删除根节点和删除中间节点没有任何区别。有一种极端情况整棵树只有一个节点删除后返回nullptr树变成空树后续访问必须判空。我刷这道题的时候测试用例里就有一组“只有一个节点且删除它”如果你直接在函数末尾写return root;而不做任何处理这组用例就会挂。模板里因为先判了root nullptr return nullptr;所以空树情形被天然覆盖了。还有一种隐蔽情况删除的值在树中根本不存在。很多人会为这种情况单独写一个搜索但递归写法天然处理了因为如果递归到nullptr还没找到就会返回nullptr一路回溯整棵树原样返回。模板里最外层的return root就是干这个的。这个分支极其重要但几乎没有人会单独测试建议你在本地自己构造一个“删除不存在值”的用例跑一遍看树有没有变化。4.3 测试用例设计思路刷完代码后很多人直接提交LeetCode返回“通过”就完事了。我建议你在本地把这几类用例都测一遍删除叶子节点验证是否是单纯置空。删除只有一个孩子的节点验证孩子是否顶替成功。删除有两个孩子的节点验证嫁接逻辑是否正确。删除根节点验证返回值是否变成新的根。删除不存在的值验证原树是否原样返回。空树删除验证是否返回nullptr。连续删除多个节点验证整棵树的完整性。这些用例如果能全部通过基本说明代码是稳的。有一个更实际的技巧把删除后的树做一次中序遍历检查序列是否依然有序。BST的性质是“中序遍历有序”这个性质可以用来做所有二叉树增删操作的验证工具。我曾经在写“把BST转换成累加树”的时候也用中序遍历结果来验证最终结果是否正确屡试不爽。5. 这一篇的真正价值从BST增删到整个系列很多人刷到BST增删的时候会下意识觉得“这不就是指针操作吗背下来完事”。但代码随想录整个二叉树篇的题目顺序是有讲究的前面你学会了递归遍历、层序遍历、各种路径问题到BST这一块题目开始加强对“有序性”的理解。二叉搜索树里每一个操作都可以用“中序遍历有序”这个性质来反推、验证、甚至设计解法。插入和删除是BST里最基础的两个修改操作但它们的地位很特殊插入是所有BST构建的底层操作从空树开始一个个插就是建树删除是所有需要动态维护有序集合的算法的基础。理解了删除的五种情况后面有几道题几乎是顺水推舟“修剪二叉搜索树”在删除的基础上把不在范围内的节点整体剪掉。核心还是递归返回值接住新子树但判断条件从key变成了区间范围。“将有序数组转换为二叉搜索树”反过来利用中序遍历有序的性质每次取中间值作为根节点。“把二叉搜索树转换为累加树”利用逆中序遍历累加节点值和增删操作共享同一种递归遍历骨架。我个人体会最深的一点是BST增删其实不在于“代码怎么背”而在于“指针怎么指”背后的空间想象能力。删除第五种情况里为什么要把左子树挂到右子树最左节点的左边因为BST的所有顺序约束都可以归结为一句话中序遍历有序。你只要保证删除后的中序遍历结果和删除前“少了被杀掉节点的值”之后的中序遍历结果完全一致那这次删除就是合法的。这个方法可以拿来推演所有你没见过的BST操作而不用背任何结论。最后分享一个刷题阶段的小技巧遇到BST的修改类题目先在中序遍历序列上模拟一遍操作再把中序序列的变化映射到树空间上指针怎么移动就一目了然了。我当年在“删除二叉搜索树中的节点”这下了一番功夫画过不下十棵树的嫁接过程画完之后后面所有BST题目都没再被指针困住过。
