给定一个二叉搜索树的根节点 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
输出: []

解答 & 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    // 寻找根为 root 的这棵二叉搜索树的最小值节点，即最左边的节点
    TreeNode* findMinNode(TreeNode* root)
    {
        TreeNode* cur = root;
        while(cur->left != nullptr)
            cur = cur->left;
        return cur;
    }
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root == nullptr)
            return nullptr;

        // 如果当前节点的值 > key，则递归在左子树中继续查找并删除
        if(root->val > key)
            root->left = deleteNode(root->left, key);
        // 如果当前节点的值 < key，则递归在右子树中继续查找并删除
        else if(root->val < key)
            root->right = deleteNode(root->right, key);
        // 如果当前节点的值 == key，则要删除当前节点，分为三种情况
        else        // root->val == key
        {
            // 情况 1：root 节点是叶子节点，则直接删除
            if(root->left == nullptr && root->right == nullptr)
            {
                delete root;
                return nullptr;
            }
            // 情况 2：root 节点有一个子节点为空，则直接用另一个非空子节点顶替 root
            else if(root->left == nullptr || root->right == nullptr)
            {
                TreeNode* replaceNode = root->left == nullptr ? root->right : root->left;
                delete root;
                return replaceNode;
            }
            // 情况 3：root 节点两个子节点都非空，则找到右子树的最左节点（最小值），顶替 root
            else    // root->left == nullptr && root->right == nullptr
            {
                // 获取右子树最小值节点（最左节点）
                TreeNode* minNode = findMinNode(root->right);
                // 用最小值节点的值替换 root 节点的值
                root->val = minNode->val;
                // 递归删除原最小值节点
                root->right = deleteNode(root->right, minNode->val);
            }
        }
        return root;      
    }
};

复杂度分析：设树的高度为 h

• 时间复杂度 O(h)
• 空间复杂度 O(h)：递归栈深度

执行结果：

执行结果：通过

执行用时：36 ms, 在所有 C++ 提交中击败了 39.88% 的用户
内存消耗：31.9 MB, 在所有 C++ 提交中击败了 34.51% 的用户