LeetCode 450. 删除二叉搜索树中的节点

2026-04-23 HGNULB 约 6 分钟

文章信息 17 个分类 3 个标签

分类

LeetCode CodeTop 中等未解决 20-50 字节跳动微软美团阿里巴巴快手腾讯猿辅导百度华为亚马逊虾皮 LeetCode 75

题目描述

✅ 450. 删除二叉搜索树中的节点

题意分析

输入是一棵二叉搜索树的根节点和一个目标值 key，要求把值等于 key 的那个节点从树里去掉，然后返回处理后整棵树的根节点。题目只保证树里的值互不相同，并不保证 key 一定存在。

「二叉搜索树」这四个字给了两个信号。第一个信号关于查找：任意节点的左子树全部小于它、右子树全部大于它，所以拿 key 和当前节点比一次大小，就能确定目标只可能在左边或只可能在右边，根本不需要两边都找。第二个信号关于结果：题目要的不是「把这个节点标记成已删除」，而是删完之后剩下的结构仍然是一棵合法的二叉搜索树，中序遍历依旧递增。

这两个信号是有主次的。查找那一半几乎是白送的，真正的难点全在「删完还得合法」上——一个节点被摘走，它原来占据的位置需要有人补上，补错了整棵树的有序性就塌了。

返回值的设计也值得留意：函数返回的是「新的子树根」而不是布尔值，这意味着删除有可能改变根，调用方必须用返回值重新挂接，而不能假设原来的指针还有效。

边界上要考虑：树为空；key 在树中不存在，此时应原样返回；被删的恰好是根节点；被删节点的孩子数量为 0、1 或 2。空树和 key 不存在其实是同一种情况——递归下探到空指针就说明没找到。

解法：递归利用 BST 性质删除节点

核心思路

问题关键：BST 能用大小关系在一条路径上定位 key，真正困难的是删除后如何重新连接子树，并继续保持中序序列严格递增。递归函数应返回“删除后的子树新根”，父节点必须接住这个返回值。

为什么这样删：命中节点后，若至多有一个孩子，直接让非空孩子顶替它；若有两个孩子，选择右子树最小节点（中序后继）作为替身。后继没有左孩子，把它的值复制到当前节点后，再从右子树删除后继，就把复杂情况归约成了至多一个孩子的情况。使用左子树最大节点（前驱）完全对称。

不变量：deleteNode(root, key) 返回的仍是合法 BST，其中包含原子树除 key 外的全部节点。key 较小时只修改左子树，较大时只修改右子树；命中后，单孩子上移不会改变其值域。双孩子时，后继大于整棵左子树且小于右子树其余节点，替换后两侧仍满足 BST 约束。

正确性：每个分支都保持上述不变量，递归返回到根时，中序序列恰好是原序列删除 key；若 key 不存在，递归在空节点结束，原树不变。

解题步骤

空节点直接返回 null，表示未找到 key 或原树为空。

key < root.val 时递归删除左子树，并将返回值重新赋给 root.left；key > root.val 时对称处理右子树。

命中后，左孩子为空就返回右孩子，右孩子为空就返回左孩子；这两句同时覆盖叶子节点。

两个孩子都存在时，在右子树中一路向左找到后继，复制其值，再从右子树删除这个后继。

返回当前子树的新根。

口述样例：[5,3,6,2,4,null,7]，key = 3。沿左侧找到 3，它有两个孩子；后继是 4，用 4 覆盖 3，再删掉右子树原来的 4，中序序列从 2,3,4,5,6,7 变为 2,4,5,6,7。

代码实现

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 successor = root.right;
            while (successor.left != null) {
                successor = successor.left;
            }
            root.val = successor.val;
            root.right = deleteNode(root.right, successor.val);
        }
        return root;
    }
}

func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }
    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 == nil {
            return root.Right
        }
        if root.Right == nil {
            return root.Left
        }

        successor := root.Right
        for successor.Left != nil {
            successor = successor.Left
        }
        root.Val = successor.Val
        root.Right = deleteNode(root.Right, successor.Val)
    }
    return root
}

复杂度分析

时间复杂度：$O(h)$，h 为树高。定位目标、寻找后继及删除后继都只沿树中的路径移动；平衡树为 $O(\log n)$，退化树最坏为 $O(n)$。

空间复杂度：$O(h)$，来自递归栈；平衡树为 $O(\log n)$，退化树最坏为 $O(n)$。

关键点总结

修改树结构时，递归函数返回“处理后的子树根”，调用方必须重新挂接。

叶子和单孩子节点可统一为：左空返回右，右空返回左。

双孩子节点用中序后继或前驱替换，把复杂删除归约为简单删除。

本解法复制节点值；若业务要求保留节点身份，应改为真正摘取并移接后继节点。

易错点总结

递归后不接返回值：删除子树根时，新根无法挂回父节点。

双孩子时直接返回某个孩子：例如删除 [5,3,6,2,4] 中的 3，会丢失 2 或 4。

把右孩子误当作后继：右子树根未必最小，必须一路向左找到底。

复制后继值后忘记删除原后继：树中会出现重复值，节点总数也没有减少。

删除后继时仍传原 key：应传 successor.val，否则右子树中的重复后继不会被删掉。

漏掉空节点终止条件：空树或 key 不存在时会发生空指针错误。

相似题目

题目	难度	考察点
700. 二叉搜索树中的搜索	简单	只走查找路径，不修改结构，本题的前半段
701. 二叉搜索树中的插入操作	中等	插入只需挂到空位，无需情形分类，与删除互为逆操作
285. 二叉搜索树中的中序后继	中等	单独求中序后继，覆盖右子树为空需回溯祖先的情况
669. 修剪二叉搜索树	中等	按区间批量删除，越界时直接用单侧子树替换整棵子树
98. 验证二叉搜索树	中等	反向检验：用上下界判断结构是否合法，可验证删除结果
230. 二叉搜索树中第 K 小的元素	中等	利用中序递增按序号取值，不涉及结构变更