Share the solution from Algorithms by ROBERT SEDGEWICK and KEVIN WAYNE


  • 0
    E
    class Solution {
    public:
        TreeNode* deleteNode(TreeNode* root, int key) {
            root = dlt(root, key);
            return root;
        }
    private:
    
        TreeNode* dlt(TreeNode* root, int key){
            if (!root) {
                return nullptr;
            }
            if (root->val < key) {
                root->right = deleteNode(root->right, key);
            }else if(root->val > key){
                root->left = deleteNode(root->left, key);
            }else{
                if (!root->left) {
                    return root->right;
                }
                if (!root->right) {
                    return root->left;
                }
                
                auto minNode = min(root->right);
                root->val = minNode->val;
                root->right = deleteMin(root->right);
            }
            return root;
        }
        
        TreeNode* min(TreeNode* root){
            if (!root) {
                return nullptr;
            }
            while (root->left) {
                root = root->left;
            }
            return root;
        }
        
        TreeNode* deleteMin(TreeNode*root){
            if (!root->left) {
                return root->right;
            }
            root->left = deleteMin(root->left);
            return root;
        }
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.