树与图中等2 种解法
#450删除二叉搜索树中的节点
删除二叉搜索树中值为 key 的节点，并保持搜索树性质。
#二叉搜索树#递归#迭代
原题
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
- 首先找到需要删除的节点；
- 如果找到了，删除它。
示例 1:
输入：root = [5,3,6,2,4,null,7], key = 3 输出：[5,4,6,2,null,null,7] 解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。 另一个正确答案是 [5,2,6,null,4,null,7]。
示例 2:
输入: root = [5,3,6,2,4,null,7], key = 0 输出: [5,3,6,2,4,null,7] 解释: 二叉树不包含值为 0 的节点
示例 3:
输入: root = [], key = 0 输出: []
提示:
- 节点数的范围
[0, 104]. -105 <= Node.val <= 105- 节点值唯一
root是合法的二叉搜索树-105 <= key <= 105
进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。
解题主线
- 删除目标后，可让右子树上位，并把原左子树挂到右子树最小节点的左侧。
解法 1：递归定位与重接
利用 BST 定位目标，递归返回删除后的子树根并回接给父节点。
-
时间复杂度： O(h)
-
空间复杂度： O(h)
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
// 利用 BST 有序性只递归目标可能所在的一侧，并回接新的子树根。
if (key < root.val) root.left = deleteNode(root.left, key);
else if (key > root.val) root.right = deleteNode(root.right, key);
else return removeRoot(root);
return root;
}
private TreeNode removeRoot(TreeNode node) {
// 没有右子树时，左子树可直接顶替被删根。
if (node.right == null) return node.left;
TreeNode successor = node.right;
// 右子树最小节点没有左孩子，可安全承接原左子树。
while (successor.left != null) successor = successor.left;
successor.left = node.left;
return node.right;
}
}解法 2：迭代定位与重接
维护 parent/current 找到目标，再把替代子树挂回父节点对应方向。
-
时间复杂度： O(h)
-
空间复杂度： O(1)
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
TreeNode parent = null;
TreeNode current = root;
// parent 始终是 current 的父节点，搜索方向由 BST 大小关系唯一确定。
while (current != null && current.val != key) {
parent = current;
current = key < current.val ? current.left : current.right;
}
if (current == null) return root;
TreeNode replacement = removeRoot(current);
// 删除根节点时没有父节点，替代子树直接成为新根。
if (parent == null) return replacement;
if (parent.left == current) parent.left = replacement;
else parent.right = replacement;
return root;
}
private TreeNode removeRoot(TreeNode node) {
if (node.right == null) return node.left;
TreeNode successor = node.right;
// 将左子树挂到右子树最小节点下，仍保持所有值的有序关系。
while (successor.left != null) successor = successor.left;
successor.left = node.left;
return node.right;
}
}边界与易错点
- 原迭代入口错误地反复使用 root.left/root.right，必须从 current 继续移动。
- 删除根节点时没有父节点，需要单独返回替代子树。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/tree/Q450_deleteNodeBST.java