Leetcode 450. Delete node in binary search tree [binary search tree]

subject

Ideas

If the value of the node to be deleted is greater than the current root node , Then the right subtree is recursively deleted ; If the value of the node to be deleted is less than the current root node , Recursively delete the left subtree ; If the current node is the node to be deleted , You need to consider which value replaces the value of the current root node :

1. If the right subtree is not empty , Assign the smallest value in the right subtree to the current root node ;
2. If the right subtree is empty , But the left subtree is not empty , Assign the maximum value in the left subtree to the current node ;
3. If the left and right subtrees are empty , Then set the current node to null

Code

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

Execution results