力扣450题：删除二叉搜索树中的节点 - 递归解法详解

内容简介

本文详细解析了力扣450题"删除二叉搜索树中的节点"的递归解法。通过递归遍历二叉搜索树并根据不同情况处理节点删除操作，实现了BST节点的精确删除。文章包含完整注释代码、算法思路讲解和复杂度分析，帮助读者掌握二叉搜索树操作的核心技巧。

算法思路

一、查找节点‌：根据BST性质递归查找目标节点

‌二、删除情况处理‌：

    1.无子节点：直接删除

    2.只有左/右子树：用子树替代当前节点

    3.有两个子节点：用右子树最小节点替代当前节点

‌三、递归调整‌：递归处理子树删除后的结构调整

代码实现（带详细注释）

class Solution {
public:
    // 查找子树最小节点(最左节点)
    TreeNode* minnode(TreeNode* root) {
        if(!root || !root->left) return root;  // 终止条件：无左子节点
        return minnode(root->left);            // 递归查找左子树
    }
    
    // 删除BST节点的递归函数
    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 {  // 找到目标节点
            // 情况1：无子节点或仅有一个子节点
            if(!root->right) return root->left;  // 只有左子树
            if(!root->left) return root->right;  // 只有右子树
            
            // 情况2：有两个子节点
            TreeNode* minRight = minnode(root->right);  // 找到右子树最小节点
            root->val = minRight->val;  // 用最小节点值替换当前节点
            root->right = deleteNode(root->right, minRight->val);  // 删除右子树中的最小节点
        }
        return root;  // 返回调整后的子树根节点
    }
};

复杂度分析

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

最坏情况(树退化为链表)：O(n)

平衡BST情况：O(log n)

‌空间复杂度‌：O(h)，递归栈空间

优化方向

‌迭代实现‌：可以改用栈或指针操作消除递归

‌平衡优化‌：删除后检查并维护BST平衡性

‌错误处理‌：添加对无效输入的检查

总结

BST节点删除是二叉树操作的重要问题，通过递归处理不同删除情况，可以高效维护BST的结构特性。理解这种解法有助于掌握BST的核心操作和递归算法的应用技巧。