如何在二叉搜索树中删除一个节点？

简化版

先按查找找到要删的节点，然后分三种情况：① 叶子节点——直接删；② 只有一个孩子——用那个孩子顶替自己；③ 有两个孩子——用中序后继（右子树里最小的节点）或中序前驱（左子树里最大的）来替换自己的值，再去删掉那个后继/前驱节点。核心是删除后仍要保持 BST 的有序性。

详细版

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 {                                   // 找到要删的节点
        // 情况 1&2：至多一个孩子，直接用孩子（或 null）顶替
        if (root.left == null)  return root.right;
        if (root.right == null) return root.left;
        // 情况 3：两个孩子，找右子树最小节点（中序后继）
        TreeNode succ = root.right;
        while (succ.left != null) succ = succ.left;
        root.val = succ.val;                 // 用后继的值覆盖当前节点
        root.right = deleteNode(root.right, succ.val);  // 再删掉那个后继
    }
    return root;
}

三种情况：

情况	处理
叶子（无孩子）	直接删（返回 null 给父节点）
只有一个孩子	用该孩子替代自己
有两个孩子	用中序后继（右子树最小）的值替换，再删那个后继

完整版教学

一、删除为什么比查找、插入难

查找和插入都不改变已有节点的位置，而删除要「挖掉」一个节点，还得让剩下的树依然是合法 BST（中序仍升序）。挖掉叶子简单，但挖掉一个内部节点会留下一个「洞」，必须找一个合适的节点来填这个洞，且填完不能破坏有序性。三种情况就是按「被删节点有几个孩子」分类讨论。

二、情况 1：叶子节点

被删节点没有孩子，直接移除即可——让它的父节点指向 null。代码里表现为「左右都为空时返回 null」（其实被情况 2 的两行覆盖了：left == null 时返回 right，而 right 也是 null，正好返回 null）。

三、情况 2：只有一个孩子

被删节点只有左孩子或只有右孩子，那就让这个唯一的孩子直接顶替它的位置（父节点越过被删节点，直接指向它的孩子）。因为子树整体的大小关系不变，顶替上来后仍满足 BST。代码：root.left == null 就返回 root.right，反之返回 root.left。

四、情况 3：有两个孩子（关键）

这是难点。被删节点有左右两棵子树，不能简单让某个孩子顶替。解决办法：找一个「值最接近它」的节点来替换，这样替换后有序性不变。有两个天然人选：

中序后继：比它大的最小节点 = 右子树中最左（最小）的节点。
中序前驱：比它小的最大节点 = 左子树中最右（最大）的节点。

以中序后继为例：把后继的值复制到当前节点（洞被填上、有序性保持），然后问题转化为「在右子树里删掉那个后继节点」。而后继节点必然没有左孩子（它是右子树最左的），所以删它只会落到情况 1 或 2，简单收尾。这就是为什么用后继/前驱——它把「删两个孩子的节点」化简成了「删一个至多一个孩子的节点」。

五、易错点与复杂度

必须用中序后继或前驱，用别的节点替换会破坏有序性。
复制值之后，别忘了递归删除右子树里的那个后继，否则会有重复节点。
用后继就到右子树找最小、用前驱就到左子树找最大，别记反。
复杂度 O(h)：查找 + 找后继都沿一条路径，平衡时 O(log n)、最坏 O(n)。

六、常见误区与追问

考点	正确口径
叶子节点	直接删除，父节点对应指针置空
一个孩子	用唯一孩子顶替当前节点
两个孩子	用中序后继或前驱替换，再删除后继/前驱

delete(key):
  if key < root.val: root.left = delete(root.left, key)
  if key > root.val: root.right = delete(root.right, key)
  else: handle 0/1/2 children

删除两个孩子的节点时，真正被物理删除的通常是后继或前驱，而不是原节点位置。

误区：找到节点后直接丢掉整棵子树。 删除必须保持 BST 性质和其余节点可达，不能破坏未删除的子树。
误区：两个孩子时随便找一个子节点顶上来。 必须找中序后继或前驱，才能保证替换后左边仍小、右边仍大。
误区：复制后继值后不用删除后继节点。 复制值只完成替换，还会留下重复节点，必须继续在右子树删除那个后继。
追问：为什么常用右子树最小值做后继？ 它是所有大于当前值的节点里最小的，放到当前位置不会破坏左右边界。
追问：递归删除为什么要返回根节点？ 删除可能改变当前子树根，例如只有一个孩子时要把孩子返回给父节点接上。
追问：复杂度由什么决定？ 查找和调整沿树高进行，时间 O(h)，平衡时 O(log n)，退化时 O(n)。

七、加强记忆

BST 删除分三种：叶子直接删；一个孩子用孩子顶替；两个孩子用**中序后继（右子树最小）**或前驱（左子树最大）的值替换当前节点，再去删那个后继/前驱。用后继/前驱是因为它值最接近、替换后有序性不变，且后继必无左孩子、删它退化成简单情况。别忘了复制值后递归删掉后继。O(h)。

简化版

详细版