本文共 1374 字，大约阅读时间需要 4 分钟。

二叉搜索树（BST）的删除操作通常分为两步：首先找到需要删除的节点，然后删除它。为了保持树的性质，删除操作必须确保新的树仍然是二叉搜索树。

删除操作步骤

代码实现

public class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return root;
        }
        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;
            } else if (root.right == null) {
                return root.left;
            }
            root.val = minValue(root.right);
            root.right = deleteNode(root.right, root.val);
        }
        return root;
    }
    private int minValue(TreeNode root) {
        int minVal = root.val;
        while (root.left != null) {
            minVal = root.left.val;
            root = root.left;
        }
        return minVal;
    }
}

代码解释

• deleteNode方法：递归寻找并删除键值对应的节点。
  • 如果键值小于当前节点值，递归处理左子树。
  • 如果键值大于当前节点值，递归处理右子树。
  • 如果键值等于当前节点值，处理该节点的左、右子树情况。
    • 如果只有左子树，返回右子树。
    • 如果只有右子树，返回左子树。
    • 否则，找到右子树的最小值节点并删除它。
• minValue方法：递归寻找右子树中的最小值节点。

这种方法确保了删除操作的时间复杂度为O(h)，其中h是树的高度，符合题目要求。代码结构清晰，逻辑严谨，适用于各种二叉搜索树删除场景。

转载地址：http://rlniz.baihongyu.com/