树与图中等2 种解法

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

删除二叉搜索树中值为 key 的节点，并保持搜索树性质。

#二叉搜索树#递归#迭代

解题主线

删除目标后，可让右子树上位，并把原左子树挂到右子树最小节点的左侧。

解法 1：递归定位与重接

利用 BST 定位目标，递归返回删除后的子树根并回接给父节点。

时间复杂度

O(h)

空间复杂度

O(h)

450. 删除二叉搜索树中的节点 · 递归定位与重接

java

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;
        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;
    }
}

利用 BST 定位目标，递归返回删除后的子树根并回接给父节点。

解法 2：迭代定位与重接

维护 parent/current 找到目标，再把替代子树挂回父节点对应方向。

时间复杂度

O(h)

空间复杂度

O(1)

450. 删除二叉搜索树中的节点 · 迭代定位与重接

java

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;
        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;
    }
}

维护 parent/current 找到目标，再把替代子树挂回父节点对应方向。

边界与易错点

原迭代入口错误地反复使用 root.left/root.right，必须从 current 继续移动。
删除根节点时没有父节点，需要单独返回替代子树。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/tree/Q450_deleteNodeBST.java