Easy understand C++ sol with explanation and beat 99%.


  • 1
    D
    1. find the element recursively using DeleteNode().
    2. remove the element and find the next element to replace the current spot using reshape() and rotate().
    3. join the left and right subtree whose parent is removed using joinLR().
    public:
        void Rotate(TreeNode* & root){
            TreeNode* tmp = root->left; 
            root->left = tmp ->right;
            tmp->right = root;
            root = tmp;
        }
        void Reshape(TreeNode* &root){
            if( root ->left != 0)
                Reshape(root->left);
            else return;
            Rotate(root);
        }
        TreeNode* joinLR(TreeNode* l, TreeNode* r){
            if(r == 0) return l;
            Reshape(r); r->left = l;
            return r;
        }
        void DeleteNode(TreeNode* &root, int key){
            if(root == nullptr) return;
            int val = root->val;
            if(val < key)  DeleteNode(root->right, key);
            if(val > key)  DeleteNode(root->left, key);
            if(val == key){
                TreeNode* tmp = root;
                root = joinLR(root->left, root->right);
                delete tmp;
            }
        }
        TreeNode* deleteNode(TreeNode* root, int key) {
            if(root == nullptr) return root;
            DeleteNode(root, key);
            return root;
        }
    };
    
    
    ![alt text](https://www.dropbox.com/s/ts9dk4rjmc5u9m7/Screenshot%202017-01-28%2013.42.35.png?dl=0)

Log in to reply
 

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