1. 先把题目读懂删除BST节点为什么是递归题的分水岭刷二叉树刷到一定阶段大家都会卡在同一个地方删除二叉搜索树中的节点。LC450这道题我第一遍做的时候五个分类情况绕得我头晕写出来的代码自己都害怕。后来把所有情况整理成一张表发现递归解法其实就那么点东西——关键是你要想明白两个问题递归函数到底返回什么以及左右子树都存在时谁来顶替被删的节点。今天就把这道题从读题到AC的完整过程拆开揉碎了讲一遍适合正在刷树的读者也适合面试前临时抱佛脚的人。题目本身不复杂给一棵二叉搜索树的根节点 root 和一个整数 key要求在树中删除值为 key 的节点最后返回删除完成后这棵树的根节点。如果树上根本没有这个值那就原样返回。看起来平平无奇但它几乎是所有BST操作里最容易写错的一道题因为删除一个节点不像在数组里挖掉一个元素那么简单你要保证删完以后剩下的仍然是一棵合法的二叉搜索树。先快速过一遍BST的基本约束这个必须烂熟于心任意节点的左子树里所有值都小于该节点右子树里所有值都大于该节点而且这棵树的子树本身也是BST也就是说这个性质是递归自洽的。因为有了这个约束BST的中序遍历结果一定是有序递增的这也是很多BST题目的突破口。删除操作之所以麻烦是因为它有三个层次的问题。第一层你得先找到目标节点这个好办利用BST的有序性从根开始二分查找。第二层找到之后怎么处理目标节点的孩子目标节点的孩子情况不同处理方式完全不同。第三层删完之后父节点那边如何接住这个变化因为删除可能导致子树根节点改变上一层的指针必须跟着更新。递归解法巧妙就巧妙在第三层的问题用返回值设计解决了我们只需要关心当前子树删除完之后该返回什么而不用在外部手动维护父节点的引用。很多新手写这道题觉得难其实是把三件事搅在了一起。我们先把这三件事拆开分而治之后面写代码就是水到渠成的事。2. 核心思路拆解删除节点的五种情况逐一过一遍2.1 情况一目标节点不存在递归到底自然结束这是最简单的情况。从根节点开始如果当前节点是空说明已经递归到叶子下面还没找到 key直接返回 null 就行。如果 key 比当前节点值小就递归去左子树找比当前节点大就去右子树找。这一步和BST查找完全一样是一个向下的二分过程。这里注意一个细节查找路径上经过的每一个节点它的指向关系都要被重新“接住”。什么意思呢比如 root.left 这一侧经历了递归删除删除后左子树结构可能变了所以当前节点的 left 指针必须更新为递归调用的返回值。这就是递归删除和递归查找唯一的差异点查找只读不改而删除要把每一层递归的结果重新赋回去。可以用一句口诀记住递归函数的返回值就是“删除操作完成后这棵子树新的根节点”。无论是继续向下搜索时把返回值赋给 root.left 或 root.right还是最终回到最初调用处把返回值作为整棵树的新根都是这句话在起作用。2.2 情况二目标节点是叶子节点直接让它“消失”当你递归找到了 key 对应的节点也就是 root.val key 的时候战斗才真正开始。第一种简单场景这个节点没有左孩子也没有右孩子就是一个叶子。直接返回 null 给上一层上一层收到 null 后把它赋给对应的 left 或 right 指针等于这个节点就从树里摘除了。举个直观的例子一棵树里要删掉值为 2 的叶子节点它挂在值为 3 的节点左边。递归到 2 这个节点时发现左右都空于是返回 null。回到值为 3 的节点代码执行 root.left deleteNode(root.left, key)此时 deleteNode 返回了 null所以 root.left 变成 null2 就被移除了。整个过程干净利落不需要任何额外的指针操作。2.3 情况三目标节点只有一只“胳膊”让子树直接顶上来如果目标节点只有一个非空孩子无论是只有左孩子还是只有右孩子处理方式也很直接返回那个非空孩子让它替代目标节点的位置。很多教科书会把这种情况分成两个小类实际上本质一样都是“用唯一的孩子顶替父节点”。我经常打一个比方这就像公司里一个小组长离职了他手下只有一个骨干员工那就让这个骨干直接接替组长位置不需要从别的部门调人过来。原来的领导和下属关系都不变只是中间换了个顶点。代码上就更简单了判断 root.left null 就直接返回 root.right反之 root.right null 就返回 root.left。这里有个初学者容易踩的小坑就是忘了先判断为空再返回直接访问另一个孩子的子节点导致空指针异常后面我专门讲。2.4 情况四目标节点左右孩子都在必须“找替身”过渡这是删除BST节点真正的难点所在。如果一个节点同时有左子树和右子树你不能简单让某一颗子树顶替因为顶上来之后另一颗子树就没地方放了。如果直接让左子树顶上来右子树里所有值都比被删节点大而左子树顶上来后它就成了根右子树必须挂在它右边但右子树里可能有些值比左子树的最大值还大结构就会乱。正确的思路是找一个“替身节点”替换被删节点的值然后删掉那个替身节点。这个替身有两种选择左子树中的最大值节点也就是左子树最右边的那个节点通常叫前驱节点或者右子树中的最小值节点也就是右子树最左边的那个节点通常叫后继节点。这两种选法都能保证替换之后整棵树仍然满足BST的性质。我自己更常用后继节点也就是去右子树里找最小的那个节点。原因很简单BST的删除目标节点是 key它的右子树的最小节点一定比左子树所有节点都大又比右子树其他节点都小拿它顶替被删节点左子树全挂它左边右子树其他节点全挂它右边性质稳如泰山。选前驱也同理只是方向反一下。具体操作分两步走第一步找到后继节点把它的值复制到当前被删节点上第二步递归去右子树中删除这个后继节点。因为后继节点一定是右子树中最左下的节点所以它最多只有一个右孩子不可能有左孩子于是第二步的删除又退化到了情况二或情况三递归一定能够终止。2.5 五种情况的判断逻辑在代码里的组织方式很多同学困惑的是这些情况在代码里怎么组织才不会漏。我建议把查找逻辑和删除逻辑放在同一个递归函数里从上到下依次判断当前节点为空、key 小于当前值、key 大于当前值、当前值等于 key。等值分支里再嵌套三种处理即无孩子、单孩子、双孩子。这种写法的好处在于递归结构天然把“向下搜索”和“找到后处理”统一起来。你不需要在外部额外写一个循环去找父节点也不需要单独记录前一个节点。每次递归返回的都是子树新的根层层上抛最终最外层就是整棵树删完后的根节点即使根节点本身被删掉了也能正确返回新的根。这就是递归解法相对迭代解法最优雅的地方也是为什么面试官通常希望你用递归解这道题。五种情况可以用下面这张表直观对照方便记忆场景目标节点的情况处理方式返回值查找中key root.val递归去左子树删除重新接上 left当前节点查找中key root.val递归去右子树删除重新接上 right当前节点删除时左右孩子都为空直接废弃该节点null删除时只有左孩子左孩子顶替root.left删除时只有右孩子右孩子顶替root.right删除时左右孩子都有用后继值覆盖递归删后继当前节点3. Java实现递归版完整代码与逐步拆解3.1 递归函数的设计搞清楚返回值到底该给谁写这道题之前你要先把函数签名在脑子里过一遍。递归函数 deleteNode(TreeNode root, int key) 的返回值类型是 TreeNode这个返回值代表的是“以 root 为根的子树在删除了 key 之后新的子树根节点是谁”。有了这个定义所有代码逻辑就都围着它转。这个设计是整个递归解法的灵魂。举个例子假设当前 root 不是目标节点key 比 root.val 小于是递归调用 deleteNode(root.left, key)这个调用返回了左子树删除完成后的新根然后我们要把它赋给 root.left。如果左子树没发生结构变化返回的还是原来的 root.left赋值等于没变如果左子树根节点被删了返回的是顶替上来的新节点赋值之后接替关系就正确建立了。再往外层看整个函数的返回值又会被它的上一层递归接收并赋给上一层的 left 或 right。一层一层往上直到最初那次调用返回值就是整棵树删除完成后新的根节点。即使你删掉的是原始根节点新的根也会通过这样的方式浮出水面。3.2 完整Java代码先贴出来/** * 删除二叉搜索树中的节点 */ class Solution { public TreeNode deleteNode(TreeNode root, int key) { // 情况一走到空节点也没找到 key直接返回 null if (root null) { return null; } // 根据 BST 性质向对应方向递归查找 if (key root.val) { // 左子树删除后用返回值重新接上左孩子 root.left deleteNode(root.left, key); } else if (key root.val) { // 右子树删除后用返回值重新接上右孩子 root.right deleteNode(root.right, key); } else { // 找到了目标节点进入删除逻辑 // 情况二左子树为空用右子树顶替右子树为空也没关系返回 null 即可 if (root.left null) { return root.right; } // 情况三右子树为空用左子树顶替 if (root.right null) { return root.left; } // 情况四左右子树都在 // 第一步找右子树中的最小节点即中序遍历的后继节点 TreeNode successor findMin(root.right); // 第二步用后继节点的值覆盖当前节点 root.val successor.val; // 第三步递归删除右子树中原来的后继节点 root.right deleteNode(root.right, successor.val); } return root; } /** * 在以 node 为根的子树中寻找值最小的节点 * 最左侧的节点就是最小值的节点 */ private TreeNode findMin(TreeNode node) { while (node.left ! null) { node node.left; } return node; } }3.3 逐行拆解每一行代码为什么要这样写先看查找部分。key root.val 时说明目标节点在左子树里我们用递归去删除左子树里的 key然后把结果赋回 root.left。为何要赋值因为删除操作可能让左子树的根发生变化最典型的就是左子树根节点正好就是要删的节点它可能被后继节点替换也可能被某个孩子顶替导致左子树的根对象变了不赋值左子树就断了。key root.val 同理处理右子树。再看删除部分。root.left null 就返回 root.right这行代码精妙地同时覆盖了无孩子和有右孩子两种情况。如果目标节点是叶子root.right 也是 null返回 null如果目标节点有右孩子直接把右孩子返回上去顶替。所以前两行判断就把“情况二”和“情况三”合并处理了非常紧凑。root.right 为空的对称判断也一样。而到了左右孩子都存在的时候进入找后继节点逻辑。findMin 函数就是一路往左走找到右子树的最小值。拿到后继后先把这个值复制到当前节点然后递归调用 deleteNode 去删除右子树里这个后继节点。为什么要递归删除而不是直接改指针因为后继节点虽然一定没有左孩子但可能有右孩子如果不递归处理后续的接替就没人管了。用递归把“删一个最多只有右孩子的节点”这件小事交给已经写好的删除逻辑处理代码复用度最高。最后 return root 是给调用这个函数的上层节点用的当前节点如果没被删那新的子树根还是它如果被删了前面已经有过 return 让函数提前结束根本走不到这一步。所以这个 return 天然表达了“当前节点未被删除”这个语义。4. 深入理解递归等价写法、复杂度与实际调试心得4.1 用前驱节点替换多了解一种写法不吃亏前面我们用的都是右子树最小值也就是后继节点。对称地也可以找左子树的最大值即前驱节点。具体操作是findMax(root.left)然后 root.val predecessor.val接着 root.left deleteNode(root.left, predecessor.val)。两种写法哪个更好本质上没有绝对优劣但有一个隐藏的考量点如果一棵树的右子树比左子树深找后继节点会让递归多走几层反之找前驱更浅。在极端情况下如果整个树左右严重失衡选择深度较浅的那一侧找替身可以少几层递归理论上是微小的性能优化。不过大多数面试场景下用哪一种都是可以接受的只要逻辑自洽。不过我个人建议你至少在本地把前驱写法也写一遍。因为找后继的写法太常见面试官很容易预设你背了模板。能随口说出“也可以找前驱只要把 findMin 换成 findMax最后递归删左子树”这句话说明你是真的理解了BST的性质而不是死记硬背通过率会高不少。4.2 不写递归、用迭代能不能做能但代码量翻倍面试时偶尔会有面试官追问能不能用迭代法实现迭代法确实可以但会麻烦很多核心难点在于你需要额外记录父节点。因为删除操作如果删的是根节点本身树的根会变而迭代过程中你不知道这个变化怎么传回最外层。迭代思路是先用一个 cur 指针找到目标节点同时用一个 parent 指针记录它的父节点。找到之后分几种情况处理删除逻辑和递归版本的五分支其实一样但删除之后要给 parent 的 left 或 right 重新赋值。如果删除的恰好是根节点还要单独维护一个返回值因为整棵树的根都变了。我个人认为如果不是被明确要求这道题用递归就好。递归版本代码短、语义清晰、不容易漏情况。但作为扩展练习迭代法值得写一遍至少能帮你把“父节点维护”这个细节彻底想清楚对理解树的指针操作有很大帮助。4.3 时间和空间复杂度为什么说O(H)而不是O(N)递归版删除的时间复杂度是O(H)其中H是树的高度。为什么不是O(N)因为每一次递归只会选择左子树或右子树中的一个方向深入永远不会同时遍历整棵树。查找目标消耗O(H)删除阶段的后继查找又消耗O(H)合起来还是O(H)。在平衡二叉树里H约等于logN所以平均时间复杂度是O(logN)。但如果你遇到一棵完全退化成链表的树比如每个节点只有右孩子那么H就是N最坏时间复杂度退化为O(N)。这也是BST本身的结构局限性也是后来红黑树、AVL树这些自平衡树存在的意义。空间复杂度同样是O(H)因为递归调用栈的深度和递归的层数一致最坏情况下递归嵌套H层。注意递归在每一层都会创建一个新的函数栈帧虽然这个题目的常数额外空间很小但在极端不平衡的树上栈溢出的风险是真实存在的。4.4 实际调试中最重要的一个习惯手动走一遍用例我在本地调试这道题时踩过很多次坑后来养成了一个习惯拿到一个测试用例先用纸笔画树手动执行一遍算法再把代码跑一遍对拍结果。比如一棵树是 [5,3,6,2,4,null,7]要删除根节点5。手动走查一遍第一步传入根节点5key等于5进入删除分支。root.left不为空root.right也不为空。第二步findMin(root.right) 返回6因为6没有左孩子它就是右子树最小值。第三步把5的值覆盖为6。第四步递归删除右子树中的6。此时右子树根节点6的左孩子为空右孩子是7于是这个删除走到“左子树为空返回右子树”的分支返回7。第五步当前节点值已经是6右孩子被更新为7重组成一棵以6为根、左子树为原左子树、右孩子为7的新树。这个走查过程能帮你确认每一步的返回值是谁、谁接住了它。我发现绝大多数初学者写错这道题都不是逻辑不懂而是走查一遍脑子里根本不知道程序在哪个点返回了谁。建议你也试试这个笨办法真的比多看十篇题解都有用。5. 常见错误与排查技巧实录5.1 错误一递归调用后没有用返回值重新赋值这是最高频的错误。很多同学写着写着会写出类似这样的代码if (key root.val) { deleteNode(root.left, key); // 没有把返回值赋给 root.left }这段代码在逻辑上不会报错但树根本不会被修改。因为函数参数传递的是引用副本deleteNode 内部对 root.left 指针的修改不会反映到外层。你必须用 root.left deleteNode(root.left, key) 把新子树根接回来删除才算真正生效。这个错误的隐蔽之处在于如果删除的是叶子节点你从测试结果看可能感觉树没变但你说不清哪里不对。排查方式很简单打印中序遍历结果对比删除前后的序列。5.2 错误二后继节点删除不干净树里出现两个相同值用后继节点覆盖被删节点之后很多人忘了第二步递归删除后继节点本身导致右子树里那个最小值节点还留在原地。表现在中序遍历里就是出现了两个一模一样的值而且整棵树仍然满足大小关系容易骗过眼睛。我排查过这个错误当时测试用例是删除一个有两个孩子的节点输出一看中序遍历多了个重复值。问题就出在只写了两步找后继、覆盖当前值少了第三步递归删除。把删除后继这步补上一切就正常了。这类问题的本质是你没想清楚“覆盖值”和“删除节点”是两个动作。覆盖值只是把当前节点的 val 改掉原来的后继节点依然存在不下狠手删掉它树里自然有两个相同的值。永远记住BST不允许重复值的节点存在。5.3 错误三边界条件判断顺序写反导致空指针来看这段代码的错误版本if (root.right null) { return root.left; } if (root.left null) { return root.right; }表面上只是两个判断调换顺序似乎没什么问题。但细想一下如果 root 左右孩子都为 null第一个判断 root.right null 成立返回 root.left也就是 null结果正确。如果只有左孩子没有右孩子第一个判断成立返回左孩子结果也正确。这么看顺序似乎无所谓真正的问题出现在逻辑不完整的时候。很多人会先写 while 找后继再判断 child或者写成 root.left.val 直接访问才会崩溃。比如 findMin(root.right) 里如果 root.right 刚好为 null直接访问 Node null 的 left 属性就一定空指针。建议统一格式所有对子节点的访问一律先判空再深入。你只要记住一个规则删除一个节点时永远先从简单情况开始处理复杂情况里再找替身能省掉大量空指针调试时间。5.4 推荐自测用例六组用例覆盖所有分支我每次写完这题都会跑下面这几组用例覆盖了删除的全部逻辑分支你要是不知道测什么直接抄这个列表用例编号操作预期结果1空树删除任意值返回 null2删除不存在的 key返回原树3删除只有一个右孩子的节点右孩子顶替4删除只有一个左孩子的节点左孩子顶替5删除叶子节点树少一个节点6删除根节点且左右子树齐全新根为后继或前驱6. 面试变体与延伸思考这道题背后的能力模型6.1 面试官常见的三种追问方式经过几次面试之后我总结了一下这道题延伸出的提问套路提前准备好能省很多临场思考时间。第一种追问是根节点被删掉了怎么办也就是题目最精髓的返回值设计。这时候你可以直接回答递归函数返回的是子树的新根所以原始根节点即使被删除新的根也会通过 return 一层层传出来不需要外部额外处理。这个问题考察的是你是否真的理解了递归的返回值还是只背了代码。第二种追问是能不能把空间复杂度降到O(1)这其实就是引导你去写迭代法。迭代法空间O(1)的核心在于用 parent 指针记录父节点删除后手动接上。你可以顺着这个方向给出思路不需要完整写出全部代码但逻辑要清晰。第三种追问比较刁钻如果要删除多个节点呢能不能复用这个算法最简单的方案是循环调用 deleteNode 多次每次传新根进去。但要注意删除节点的顺序会影响时间复杂度比如每次删除都选择树中较深的孩子删除反复操作可能让树退化得更快。想优化的话可以一次性收集需要删除的值排序后在树中批量处理但这已经超出本题范围了。6.2 与BST其他经典题的横向联系LC450不是一道孤立的题它和BST的一整个题目家族都有关联。真正把这道题吃透你等于打通了BST递归操作的一类范式。比如LC701插入二叉搜索树用的是同一个递归范式只是从删除变成了插入插入的难度低很多找到空位挂上新节点就行。LC700搜索BST节点就更简单了只查找不修改。LC98验证BST则利用中序遍历有序性来验证思路完全不同。这几道题对比着刷你会发现一个规律BST相关的递归题核心永远在返回值与指针的重新接续上。查找题不需要修改指针但需要仔细利用有序性插入题和删除题则必须想清楚“修改后怎么把新根传回去”。掌握了LC450的返回值设计其他树的修改类题目对你来说就是个模式识别的问题。6.3 在实际工程中删除BST节点有什么现实映射刷题刷多了容易觉得这类树操作离工程很远但实际并不完全如此。凡是需要维护有序动态集合的场景几乎都会用到BST或其变种。比如数据库索引中的B树在删除键值时要处理节点下溢和重新平衡思想本质上和BST删除后的结构调整是一致的只不过B树允许一个节点有多于两个的孩子调整规则更复杂。再比如一些进程调度、路由表查找、区块链交易排序等系统里底层都会维护一棵平衡的搜索树节点的增删是高频操作。笔试里刷的这棵树可能在业务代码中就长成一个订单价格索引或者一个内存缓存的时间戳排序结构。理解了节点的删除为什么需要找前驱或后继这个核心思想你在设计类似数据结构时就不会把性质维护想得过于简单。6.4 刷完这道题建议你再做的三件事第一件把代码重构一遍改成前驱节点替代方案再跑一遍上面六组测试用例。这个练习能让你体会到对称逻辑的美感也更容易在面试中应对“换一种方式实现”的要求。第二件如果你还写得顺试试迭代法不为别的就是为了把父节点指针维护这个细节彻底搞明白。第三件把LC701、LC700、LC98这几道题连同本道题放在一天内集中刷完形成BST操作的横向对比。我个人在实际操作中的体会是这种“一拖三”的集中刷法比一天刷十道不同主题的题效果要好得多。树的题和数组链表不一样它太依赖递归思维而递归思维是靠重复刺激形成的。LC450这道题你就算今天背得再熟两周不碰照样忘但如果连带着它周边四五道题一起形成知识网络这个记忆就很难消退了。最后分享一个小技巧刷二叉树的题永远在纸上画树。我见过太多人用IDE调试各种树操作题断点打了一个又一个状态变量翻来覆去看效率还不如用手把树画出来然后手动走查。人脑对空间结构的理解能力远强于对抽象指针的追踪能力一支笔一张纸三分钟走完一个用例比你盯半小时调试窗都有用。LC450这道题尤其适合这种走查方式五种情况各画一棵小树来回切换着走几遍你就算真正掌握它了。