删除二叉搜索树中的节点

因为被删的节点下面可能还挂着一整棵子树。直接抹掉,它的孩子们就成了断线的风筝——必须想清楚谁来当这些孩子的新爸爸。

找节点和查找一模一样:key 比当前小往左走、比当前大往右走。找到后看孩子数:没孩子直接删、一个孩子让孩子顶上、两个孩子最麻烦,用「后继」顶替。

盯住下方那棵树:高亮的当前节点怎么沿路径走、找到 3 之后后继 4 怎么爬上来顶替它、最后多余的 4 怎么被删掉。

初始树 · 准备删 3：整棵树长这样。我们要删值为 3 的节点。先从根 5 开始找:3 比 5 小,该往左走。

查找 · 走到左孩子：从 5 往左,落到节点 3(5 变蓝表示路过了)。当前值正好 = key,目标找到。接下来看它有几个孩子。

判断孩子数 · 命中难例：节点 3 左边挂着 2、右边挂着 4(都标紫高亮),两个孩子都在。这是最难的情况:不能简单删,得找个「替身」顶上来。

为什么是右子树最小?因为它比被删节点的左边全大、比被删节点的右边其余全小——正好能无缝接替,顶上来后 BST 依然成立。右子树最小 = 一路往左走到底。

找后继 · 进入右子树：进入 3 的右子树,从右孩子 4 开始。要找右子树里最小的,规则是一直往左走到底。先看 4 有没有左孩子。

找后继 · 4 已无左孩子：节点 4 没有左孩子了,说明它就是右子树里最小的那个。后继 = 4 确定下来(标绿)。下一步把 4 的值搬到被删节点 3 的位置。

顶替前 · 锁定被删节点与后继：把两个主角同时标出来:要删的 3(橙)和它的替身后继 4(紫)。马上要做的就是把 4 的值搬到 3 头上。

顶替 · 把 3 的值改成 4：关键一步:把被删节点的值直接从 3 改成 4(节点位置不变,只换数字)。现在树里出现了两个 4——上面顶替用的、和右子树里原来那个。多余的得删掉。

清理 · 转去删右子树里的 4：现在的任务变成:在右子树里删掉那个原来的 4。它正好没有孩子(叶子)——这就退化成了最简单的「无孩子」情况。

清理完成 · 叶子 4 摘除：原来的叶子 4 被直接摘掉。最终树:根 5,左孩子变成了 4(它下面还挂着 2),右边 6→7 不动。删一个、补一个,BST 依然成立。

验证 · 中序遍历：验证删对没:中序遍历(左→根→右)结果该是升序。一路往左走到底,最先访问最左下的 2。

验证 · 访问 4 与 5：回到 2 的父节点 4,再回到根 5。序列 2 → 4 → 5 还是升序,左半边没问题。

验证 · 访问 6 与 7：最后访问右边的 6 和它的右孩子 7。完整中序 2 → 4 → 5 → 6 → 7,严格升序——删除后仍是合法 BST,大功告成。

两个孩子是最复杂的。剩下两种很轻松,但都得看到才放心。下面各演一遍。

情况一 · 从根找 key=2：新树 [4,2,6]。这回删叶子 2。还是从根 4 出发:2 比 4 小,往左走。

情况一 · 删叶子(无孩子)：落到叶子 2(没有任何孩子)。最省事:它的父亲那边直接接个空,把它摘掉就行,谁也不影响。

情况一 · 摘除完成：叶子 2 没了,父节点 4 的左边变空。删叶子 = 直接返回空,最简单的一种。

情况二 · 从根找 key=6：再换一棵树 [4,2,6,null,null,null,7],删 6。从根 4 出发:6 比 4 大,往右走。

情况二 · 删单孩子节点：落到 6,它只有一个孩子 7(右孩子)。办法是让唯一的孩子 7 直接顶上 6 的位置——孩子带着它自己的子树整个上移。

情况二 · 孩子顶替完成：6 被它唯一的孩子 7 顶替,接到根 4 的右边。单孩子 = 返回那个孩子。

三情况总览：三种情况一图收口:没孩子直接删、单孩子让孩子顶上、双孩子用右子树最小(后继)顶替再删后继。看孩子数选对应招,删除就一通百通。

后继(右子树最小)是所有比被删节点大的数里最小的那个——它一上位,左边照样全比它小、右边照样全比它大,顺序天衣无缝。用左子树最大(前驱)也对称成立。

雷区实演 · 返回值没接回：若只写 deleteNode(root.left, 2) 而不把结果赋回 root.left,递归算出的新子树根没人接,原来的 2 纹丝不动——看着调用了,其实啥也没删。

边界三连：key 不在树里时,一路走到空节点返回,树原样不动——不会报错也不会乱删。

面试追问：复杂度、前驱后继对称性、为何只换值,是这题面试最爱追的三点。