[450. delete nodes in binary search tree]

source ： Power button （LeetCode）

describe ：

Given the root node of a binary search tree root And a value key, Delete the key Corresponding node , And keep the property of binary search tree unchanged . Back to binary search tree （ May be updated ） Reference to the root node of .

Generally speaking , Deleting a node can be divided into two steps ：

First find the node to be deleted ;
If you find it , Delete it .

Example 1:

 Input ：root = [5,3,6,2,4,null,7], key = 3
 Output ：[5,4,6,2,null,null,7]
 explain ： Given the node value to be deleted is  3, So first we found  3  This node , Then delete it .
 The right answer is  [5,4,6,2,null,null,7],  As shown in the figure below .
 The other correct answer is  [5,2,6,null,4,null,7].

Example 2:

 Input : root = [5,3,6,2,4,null,7], key = 0
 Output : [5,3,6,2,4,null,7]
 explain :  Binary tree does not contain a value of  0  The node of 

Example 3:

 Input : root = [], key = 0
 Output : []
 

Tips :

• Range of nodes [0, 10⁴].
• -10⁵<= Node.val <= 10⁵
• Unique node value
• root Is a legitimate binary search tree
• -10⁵ <= key <= 10⁵

Method 1 ： recursive

Ideas

Code :

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

Execution time ：28 ms, In all C++ Defeated in submission 83.08% Users of
Memory consumption ：31.8 MB, In all C++ Defeated in submission 71.37% Users of
Complexity analysis
Time complexity ： O(n), among n by root Number of nodes . In the worst case , Find and delete successor Each tree needs to be traversed once .
Spatial complexity ： O(n), among n by root Number of nodes . The deepest recursion is O(n).

Method 2 ： iteration

Ideas

The recursion depth of method 1 is at most n, And most of it is by looking for a value of key The contribution of the node , The part of finding nodes can be optimized by iteration . Find and delete successor when , You can also save its parent node with a variable , Thus, one step recursive operation can be saved .

Code :

class Solution {
    
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
    
        TreeNode *cur = root, *curParent = nullptr;
        while (cur && cur->val != key) {
    
            curParent = cur;
            if (cur->val > key) {
    
                cur = cur->left;
            } else {
    
                cur = cur->right;
            }
        }
        if (!cur) {
    
            return root;
        }
        if (!cur->left && !cur->right) {
    
            cur = nullptr;
        } else if (!cur->right) {
    
            cur = cur->left;
        } else if (!cur->left) {
    
            cur = cur->right;
        } else {
    
            TreeNode *successor = cur->right, *successorParent = cur;
            while (successor->left) {
    
                successorParent = successor;
                successor = successor->left;
            }
            if (successorParent->val == cur->val) {
    
                successorParent->right = successor->right;
            } else {
    
                successorParent->left = successor->right;
            }
            successor->right = cur->right;
            successor->left = cur->left;
            cur = successor;
        }
        if (!curParent) {
    
            return cur;
        } else {
    
            if (curParent->left && curParent->left->val == key) {
    
                curParent->left = cur;
            } else {
    
                curParent->right = cur;
            }
            return root;
        }
    }
};

Execution time ：28 ms, In all C++ Defeated in submission 83.08% Users of
Memory consumption ：31.8 MB, In all C++ Defeated in submission 86.56% Users of
Complexity analysis
Time complexity ： O(n), among n by root Number of nodes . In the worst case , You need to traverse the tree once .
Spatial complexity ： O(1). The space used is constant .
author：LeetCode-Solution