LC450 Delete Node in a BST

本题链接：Delete Node in a BST

本题标签：Tree

本题难度：

方案1：

class Solution {
private:
    TreeNode* doDelete(TreeNode* node)
    {
        if(node == NULL)
            return node;
        else if(node->left == NULL)
        {
            TreeNode* temp = node->right;
            delete node;
            node = NULL;
            return temp;
        }
        else if(node->right == NULL)
        {
            TreeNode* temp = node->left;
            delete node;
            node = NULL;
            return temp;
        }
        
        TreeNode* next = node->right;
        TreeNode* pre = NULL;
        while(next->left != NULL)
        {
            pre = next;
            next = next->left;
        }
        
        next->left = node->left;
        if(node->right != next)
        {
            pre->left = next->right;
            next->right = node->right;
        }
        return next;
    }
    
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root == NULL)
            return NULL;
        
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        while(cur != NULL && cur->val != key)
        {
            pre = cur;
            if(cur->val < key)
                cur = cur->right;
            else
                cur = cur->left;
        }
        
        if(pre == NULL)
            return doDelete(cur);
        if(pre->left == cur)
            pre->left = doDelete(cur);
        else
            pre->right = doDelete(cur);
            
        return root;
    }
};

时间复杂度：

空间复杂度：