no recursion c++ o(height);

  • 0

    update: I add more comments to make this is easy to read

        TreeNode* deleteNode(TreeNode* root, int key) {
            TreeNode preroot(0);
            TreeNode* pre = &preroot;
            pre->right = root;
    //update: nothing to say just find the node with key value
            while(root != NULL && root->val != key){    
                pre = root;
                if(root->val < key)
                    root = root->right;
                    root = root->left;
    //if using this condition then the below part no necessary to check check the  root!=NULL and next != NULL
    // that two is marked as '***************************'
            // if(root == NULL)
            //     return preroot.right;    
    /*update: now we find the node with key value, then we have four situation:
    *1.node has no children
    *2.node only has left children
    *3.node only has right children
    *4. node has two children
    *situation 1-3 are easy. but situation 4 is very complex. I deal with situation 4 by take the biggest value of left child.
    *in order to make it easier, when the node has left subtree, I will take the biggest value of left subtree to the current node
    /*update:node has left children and then we get the biggest value and modified the value of the current node to the *biggest value. and then we change the problem to delete the node with biggest value in left subtree
            if(root!= NULL && root->left != NULL){   //*********don't need to check root != NULL if return early
                TreeNode* del = root->left;
                pre = root;
                while(del->right != NULL){
                    pre = del;
                    del = del->right;
                root->val = del->val;
                root = del;
    // update: now the node which need to delete only has two situation
    //update:1.node has no children
    //update:2.node only has left children 
        TreeNode* next = root;
            if(next != NULL && next->left != NULL)  //*********don't need to check next != NULL if return early      
                next = next->left;
            else if(next != NULL)
                next = next->right;
            if(pre->left == root)
                pre->left = next;
                pre->right = next;
            return preroot.right;

Log in to reply

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