Medium

题目描述

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中值为 key 的节点，并返回新的根节点（可能更新）。

删除过程可以分为两个步骤：

  1. 搜索要删除的节点
  2. 如果找到该节点，删除该节点

示例 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, 10^4]
  • -10^5 <= Node.val <= 10^5
  • 每个节点都有不同的值
  • root 是合法的二叉搜索树
  • -10^5 <= key <= 10^5

进阶： 能否在时间复杂度为 O(树的高度) 内解决？

解题思路

在二叉搜索树中删除节点是一个经典问题，需要考虑三种情况：

  1. 删除叶子节点：直接删除即可
  2. 删除只有一个子树的节点：用其子树替代该节点
  3. 删除有两个子树的节点：这是最复杂的情况，有两种处理方式：
    • 用左子树中的最大值（前驱）替代该节点
    • 用右子树中的最小值（后继）替代该节点

推荐使用递归方法，利用二叉搜索树的性质进行高效搜索。递归过程：

  • 如果要删除的值小于当前节点值，递归处理左子树
  • 如果要删除的值大于当前节点值，递归处理右子树
  • 如果找到目标节点，根据其子树情况进行相应处理

对于有两个子树的节点，我选择用右子树的最小值替代，这样能保持BST的性质。具体做法是：

  1. 找到右子树中的最小值节点
  2. 用该最小值替换当前节点的值
  3. 递归删除右子树中的最小值节点

时间复杂度为O(h)，其中h是树的高度，符合进阶要求。

代码实现

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return nullptr;
        
        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) {
                TreeNode* temp = root->right;
                delete root;
                return temp;
            } else if (!root->right) {
                TreeNode* temp = root->left;
                delete root;
                return temp;
            } else {
                // 有两个子树，找右子树的最小值
                TreeNode* minNode = findMin(root->right);
                root->val = minNode->val;
                root->right = deleteNode(root->right, minNode->val);
            }
        }
        return root;
    }
    
private:
    TreeNode* findMin(TreeNode* node) {
        while (node->left) {
            node = node->left;
        }
        return node;
    }
};

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None
        
        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            # 找到要删除的节点
            if not root.left:
                return root.right
            elif not root.right:
                return root.left
            else:
                # 有两个子树，找右子树的最小值
                min_node = self.find_min(root.right)
                root.val = min_node.val
                root.right = self.deleteNode(root.right, min_node.val)
        
        return root
    
    def find_min(self, node):
        while node.left:
            node = node.left
        return node

public 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;
            } else if (root.right == null) {
                return root.left;
            } else {
                // 有两个子树，找右子树的最小值
                TreeNode minNode = FindMin(root.right);
                root.val = minNode.val;
                root.right = DeleteNode(root.right, minNode.val);
            }
        }
        return root;
    }
    
    private TreeNode FindMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

var deleteNode = function(root, key) {
    if (!root) 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) {
            return root.right;
        } else if (!root.right) {
            return root.left;
        } else {
            // 有两个子树，找右子树的最小值
            let minNode = findMin(root.right);
            root.val = minNode.val;
            root.right = deleteNode(root.right, minNode.val);
        }
    }
    return root;
};

function findMin(node) {
    while (node.left) {
        node = node.left;
    }
    return node;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值说明
时间复杂度O(h)h 是树的高度，平均情况下为 O(log n)，最坏情况下为 O(n)
空间复杂度O(h)递归调用栈的深度，平均情况下为 O(log n)，最坏情况下为 O(n)

相关题目