删除二叉搜索树中的节点 图解题解

这道题到底在问什么

树

[5,3,6,2,4,null,7]

key

3

删后

3 被 4 顶替 → [5,4,6,2,null,null,7]

最优解：一步一步想明白

1. 3因为被删的节点下面可能还挂着一整棵子树。直接抹掉,它的孩子们就成了断线的风筝——必须想清楚谁来当这些孩子的新爸爸。
2. 4找节点和查找一模一样:key 比当前小往左走、比当前大往右走。找到后看孩子数:没孩子直接删、一个孩子让孩子顶上、两个孩子最麻烦,用「后继」顶替。
3. 5盯住下方那棵树:高亮的当前节点怎么沿路径走、找到 3 之后后继 4 怎么爬上来顶替它、最后多余的 4 怎么被删掉。
4. 6从根 5 出发找 key=3整棵树长这样。我们要删值为 3 的节点。先从根 5 开始找:3 比 5 小,该往左走。
5. 73 < 5 → 走左,来到节点 3从 5 往左,落到节点 3(5 变蓝表示路过了)。当前值正好 = key,目标找到。接下来看它有几个孩子。
6. 8节点 3 左有 2、右有 4 → 两个孩子节点 3 左边挂着 2、右边挂着 4(都标紫高亮),两个孩子都在。这是最难的情况:不能简单删,得找个「替身」顶上来。
7. 9为什么是右子树最小?因为它比被删节点的左边全大、比被删节点的右边其余全小——正好能无缝接替,顶上来后 BST 依然成立。右子树最小 = 一路往左走到底。
8. 10后继 = 节点 3 的右子树里最小值进入 3 的右子树,从右孩子 4 开始。要找右子树里最小的,规则是一直往左走到底。先看 4 有没有左孩子。
9. 114 没有左孩子 → 它就是最小节点 4 没有左孩子了,说明它就是右子树里最小的那个。后继 = 4 确定下来(标绿)。下一步把 4 的值搬到被删节点 3 的位置。
10. 12被删节点 3 ⇄ 后继 4把两个主角同时标出来:要删的 3(橙)和它的替身后继 4(紫)。马上要做的就是把 4 的值搬到 3 头上。
11. 13节点位置不动,值 3 → 4关键一步:把被删节点的值直接从 3 改成 4(节点位置不变,只换数字)。现在树里出现了两个 4——上面顶替用的、和右子树里原来那个。多余的得删掉。
12. 14问题转化:在右子树删掉后继 4现在的任务变成:在右子树里删掉那个原来的 4。它正好没有孩子(叶子)——这就退化成了最简单的「无孩子」情况。
13. 15原后继 4 删除,树接回完整原来的叶子 4 被直接摘掉。最终树:根 5,左孩子变成了 4(它下面还挂着 2),右边 6→7 不动。删一个、补一个,BST 依然成立。
14. 16中序应为严格升序验证删对没:中序遍历(左→根→右)结果该是升序。一路往左走到底,最先访问最左下的 2。
15. 172 → 4 → 5,持续升序回到 2 的父节点 4,再回到根 5。序列 2 → 4 → 5 还是升序,左半边没问题。
16. 186 → 7,全部升序 ✓最后访问右边的 6 和它的右孩子 7。完整中序 2 → 4 → 5 → 6 → 7,严格升序——删除后仍是合法 BST,大功告成。
17. 19两个孩子是最复杂的。剩下两种很轻松,但都得看到才放心。下面各演一遍。
18. 202 < 4 → 往左走新树 [4,2,6]。这回删叶子 2。还是从根 4 出发:2 比 4 小,往左走。
19. 21删 key=2,2 是叶子落到叶子 2(没有任何孩子)。最省事:它的父亲那边直接接个空,把它摘掉就行,谁也不影响。
20. 222 删除,父节点 4 左边接空叶子 2 没了,父节点 4 的左边变空。删叶子 = 直接返回空,最简单的一种。
21. 236 > 4 → 往右走再换一棵树 [4,2,6,null,null,null,7],删 6。从根 4 出发:6 比 4 大,往右走。
22. 24删 key=6,6 只有右孩子 7落到 6,它只有一个孩子 7(右孩子)。办法是让唯一的孩子 7 直接顶上 6 的位置——孩子带着它自己的子树整个上移。
23. 257 顶替 6,接回根 4 的右边6 被它唯一的孩子 7 顶替,接到根 4 的右边。单孩子 = 返回那个孩子。
24. 26无孩子 / 单孩子 / 双孩子三种情况一图收口:没孩子直接删、单孩子让孩子顶上、双孩子用右子树最小(后继)顶替再删后继。看孩子数选对应招,删除就一通百通。
25. 29后继(右子树最小)是所有比被删节点大的数里最小的那个——它一上位,左边照样全比它小、右边照样全比它大,顺序天衣无缝。用左子树最大(前驱)也对称成立。
26. 31deleteNode 调了却没赋值 → 树没变若只写 deleteNode(root.left, 2) 而不把结果赋回 root.left,递归算出的新子树根没人接,原来的 2 纹丝不动——看着调用了,其实啥也没删。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def deleteNode(self, root, key):
        if not root:              # 没找到,空树
            return None
        if key < root.val:        # 去左子树找
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:      # 去右子树找
            root.right = self.deleteNode(root.right, key)
        else:                     # 找到了,分情况
            if not root.left:     # 无左 → 右孩子顶上
                return root.right
            if not root.right:    # 无右 → 左孩子顶上
                return root.left
            succ = root.right     # 两孩子: 找右子树最小
            while succ.left:
                succ = succ.left
            root.val = succ.val   # 后继值顶替
            root.right = self.deleteNode(root.right, succ.val)
        return root

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) 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)  return root->right;
            if (!root->right) return root->left;
            TreeNode* succ = root->right;
            while (succ->left) succ = succ->left;
            root->val = succ->val;
            root->right = deleteNode(root->right, succ->val);
        }
        return root;
    }
};

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        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 == null)  return root.right;
            if (root.right == null) return root.left;
            TreeNode succ = root.right;
            while (succ.left != null) succ = succ.left;
            root.val = succ.val;
            root.right = deleteNode(root.right, succ.val);
        }
        return root;
    }
}

复杂度

面试官可能追问