LeetCode 450. 删除二叉搜索树中的节点
题目描述
题意分析
给定二叉搜索树的根节点
root和目标值key，删除值等于key的节点，返回删除后的根节点。其余节点值都要保留，结果仍须满足左子树所有值更小、右子树所有值更大的搜索树性质。若目标值不存在，树保持原样。待删节点可能是叶子、只有一个孩子，也可能同时有左右孩子；根节点本身同样可能被删除，因此返回的根不一定是原来的根。题目要求保持正确的值集合与搜索关系，不要求删除后的树形唯一。
解法：递归利用 BST 性质删除节点
核心思路
[!blue]
定义
deleteNode(root, key)返回“以root为根的子树删除目标之后的新根”。这个返回含义同时解决查找和接线：目标比当前值小，只递归左子树，并将结果接回root.left；目标更大时对称处理右子树。另一侧不可能包含目标，无需访问。找到目标后，若至多有一个孩子，可以直接返回这个孩子，让调用者用它替代当前节点。左孩子为空时返回右孩子，右孩子为空时返回左孩子；两个孩子都为空的叶子也自然返回空。留下的整棵子树仍处于相同祖先限制内，所以不会破坏搜索树性质。
有两个孩子时，不能简单丢掉其中一侧。选择右子树的最小节点，也就是当前节点的中序后继，用它的值覆盖当前值。这个值大于原左子树的所有值；从右子树删除原后继后，它又小于右子树剩下的所有值，因此新的根值能正确分隔左右两侧。
右子树的最小节点可以从右孩子出发一直向左找到。它没有左孩子，但可能有右孩子，所以再调用同一个删除函数，将它归约为前面的至多单孩子情况，并把返回的新根接回
root.right。只复制值却不删除原后继，会多保留一个相同值，不能算完成删除。未找到目标时，递归最终遇到空节点并返回空，沿途原连接重新接回，整棵树保持不变。找到目标后的接线也逐层由返回值传回，最外层返回值就是删除后的整棵树。
解题步骤
- 当前子树为空时返回空。
- 目标较小时递归左子树并接回
root.left，目标较大时递归右子树并接回root.right。- 命中目标且左孩子为空时返回右孩子；否则右孩子为空时返回左孩子。
- 两个孩子都存在时，从右孩子沿左链找到后继，复制其值。
- 在右子树中删除这个后继值，将删除后的子树根接回右侧，再返回当前根。
代码实现
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)$，来自递归栈；只改变原树的值与连接，不创建另一棵树。
关键点总结
[!green]
- 递归返回处理后的子树根，调用方必须把新根接回原来的孩子位置。
- 至多一个孩子时直接返回剩余子树；两个孩子时用中序后继替换值，再删除原后继。
- 后继选右子树的最小值，才能同时维持两侧的大小关系。
易错点总结
[!yellow]
- 忽略递归返回值，删除子树根时就无法把替代节点接回父节点。
- 双孩子时直接返回某个孩子，会把另一棵子树丢掉。
- 直接选右孩子代替后继值，可能留下比新根更小的右子树节点；必须找到右子树最左节点。
- 复制后继值后没有删除原后继，会留下重复值，节点数量也没有减少。
- 删除后继时继续传原
key，会在错误的值上查找；应传successor.val。- 把后继当作必然是叶子，直接断开它的父连接，会丢掉后继可能拥有的右子树。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 701. 二叉搜索树中的插入操作 | 中等 | 同样沿BST有序方向定位位置，本题删除两个孩子的节点时还需用前驱或后继接替。 |
| 669. 修剪二叉搜索树 | 中等 | 原题按数值区间批量裁剪BST，本题只删除一个指定值，保留其余节点的搜索关系。 |