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

Categories:

Tags:

题目描述
思路分析
1. 解法一：递归（推荐）
2. 解法二：迭代 + 子树拼接
相似题目

题目描述

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

思路分析

解法一：递归（推荐）

核心思路：

利用 BST 的有序性定位目标节点，删除时分三种情况处理：

目标值 < 当前节点：递归到左子树删除

目标值 > 当前节点：递归到右子树删除

找到目标节点，分三种子情况：

叶节点：直接返回 nil 删除

只有右子树：右子树替代当前节点

只有左子树：左子树替代当前节点

左右子树都有：找右子树最小节点（中序后继），用其值覆盖当前节点，再递归删右子树中该值

复杂度分析：

时间复杂度：O(h)，其中 h 为树的高度，平衡时 O(log n)，最坏退化为 O(n)

空间复杂度：O(h)，递归调用栈深度

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 && root.right == null) {
                return null;
            }
            // 只有右子树，右子树替代
            if (root.left == null) {
                return root.right;
            }
            // 只有左子树，左子树替代
            if (root.right == null) {
                return root.left;
            }
            // 左右子树均存在，找右子树最小节点（中序后继）
            TreeNode minNode = findMin(root.right);
            root.val = minNode.val;
            // 递归删除右子树中的中序后继节点
            root.right = deleteNode(root.right, minNode.val);
        }
        return root;
    }

    // 寻找以 node 为根的子树中的最小节点
    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

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 && root.Right == nil {
            return nil
        }
        // 只有右子树，右子树替代
        if root.Left == nil {
            return root.Right
        }
        // 只有左子树，左子树替代
        if root.Right == nil {
            return root.Left
        }
        // 左右子树均存在，找右子树最小节点（中序后继）
        minNode := findMin(root.Right)
        root.Val = minNode.Val
        // 递归删除右子树中的中序后继节点
        root.Right = deleteNode(root.Right, minNode.Val)
    }
    return root
}

// findMin 寻找以 node 为根的子树中的最小节点
func findMin(node *TreeNode) *TreeNode {
    for node.Left != nil {
        node = node.Left
    }
    return node
}

解法二：迭代 + 子树拼接

核心思路：

不使用递归，改用迭代方式找到目标节点及其父节点，删除时将左子树接到右子树最左节点的左指针上，再用右子树替换目标节点位置。

迭代遍历找到目标节点 cur 及其父节点 parent

删除 cur 时，将 cur.left 拼接到 cur.right 最左节点的左指针

用 cur.right（若为空则用 cur.left）替换父节点对应子指针

复杂度分析：

时间复杂度：O(h)，其中 h 为树的高度

空间复杂度：O(1)，仅使用常数额外指针

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode parent = null;
        TreeNode cur = root;
        // 迭代查找目标节点
        while (cur != null && cur.val != key) {
            parent = cur;
            if (key < cur.val) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        // 未找到目标节点
        if (cur == null) {
            return root;
        }
        // 将左子树拼接到右子树最左节点
        TreeNode replacement = merge(cur.left, cur.right);
        // 更新父节点指针，或更新根节点
        if (parent == null) {
            return replacement;
        }
        if (parent.left == cur) {
            parent.left = replacement;
        } else {
            parent.right = replacement;
        }
        return root;
    }

    // 将 left 子树拼接到 right 子树最左节点的左指针，返回合并后根
    private TreeNode merge(TreeNode left, TreeNode right) {
        if (right == null) {
            return left;
        }
        // 找到右子树最左节点
        TreeNode minNode = right;
        while (minNode.left != null) {
            minNode = minNode.left;
        }
        minNode.left = left;
        return right;
    }
}

func deleteNode(root *TreeNode, key int) *TreeNode {
    var parent *TreeNode
    cur := root
    // 迭代查找目标节点
    for cur != nil && cur.Val != key {
        parent = cur
        if key < cur.Val {
            cur = cur.Left
        } else {
            cur = cur.Right
        }
    }
    // 未找到目标节点
    if cur == nil {
        return root
    }
    // 将左子树拼接到右子树最左节点，得到替代节点
    replacement := mergeNodes(cur.Left, cur.Right)
    // 更新父节点指针，或更新根节点
    if parent == nil {
        return replacement
    }
    if parent.Left == cur {
        parent.Left = replacement
    } else {
        parent.Right = replacement
    }
    return root
}

// mergeNodes 将 left 拼接到 right 最左节点的左指针，返回合并后根
func mergeNodes(left, right *TreeNode) *TreeNode {
    if right == nil {
        return left
    }
    // 找到右子树最左节点
    minNode := right
    for minNode.Left != nil {
        minNode = minNode.Left
    }
    minNode.Left = left
    return right
}

相似题目

题目	难度	考察点
700. 二叉搜索树中的搜索	简单	BST 性质 / 递归查找
701. 二叉搜索树中的插入操作	中等	BST 性质 / 递归插入
98. 验证二叉搜索树	中等	BST 性质 / 中序遍历
235. 二叉搜索树的最近公共祖先	中等	BST 性质 / 递归
669. 修剪二叉搜索树	中等	BST 性质 / 递归修剪
230. 二叉搜索树中第 K 小的元素	中等	BST 中序遍历
1305. 两棵二叉搜索树中的所有元素	中等	BST 中序遍历 / 合并

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/29214620