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

题目描述

本题目来自 LeetCode 上的『450.删除二叉搜索树中的节点』

给定一个二叉搜索树，要求删除指定值对应的结点。

示例 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]。

题解

经典的二叉搜索树删除节点问题。

代码

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) {
            return nullptr;
        }
        if (key > root->val) {
            root->right = deleteNode(root->right, key);
        } else if (key < root->val) {
            root->left = deleteNode(root->left, key);
        } else {
            if (root->left == nullptr) {
                return root->right;
            }
            if (root->right == nullptr) {
                return root->left;
            }
            TreeNode* curr = root->right;
            while (curr->left) {
                curr = curr->left;
            }
            curr->left = root->left;
            root = root->right;
        }
        return root;
    }
};

复杂度分析

• 时间复杂度：$O(n)$

• 空间复杂度：$O(1)$