30 lines C++, elegantly using TreeNode**, 35ms


  • 1

    The basic idea is to use the smallest element of left subtree of key node(aka. the left most node of the key node's right sub tree) to replace it.
    Use TreeNode** would make your code much cleaner.

    TreeNode* deleteNode(TreeNode* root, int key) {
        TreeNode** now=&root;
        while((*now)!=nullptr){
            if(key > (*now)->val){
                now=&((*now)->right);
            }else if(key < (*now)->val){
                now=&((*now)->left);
            }else{
                break;
            }
        }
        if((*now)!=nullptr){
            if((*now)->right==nullptr){
                (*now)=(*now)->left;
            }else if((*now)->left==nullptr ){
                (*now)=(*now)->right;
            }else{
                TreeNode** leftMostPtr=&((*now)->right);
                while((*leftMostPtr)->left!=nullptr){
                    leftMostPtr=&((*leftMostPtr)->left);
                }
                TreeNode* newNode=(*leftMostPtr);
                
                (*leftMostPtr)=(*leftMostPtr)->right;
                newNode->left=(*now)->left;
                newNode->right=(*now)->right;
                (*now)=newNode;
            }
        }
        return root;
    }
    

  • 0
    W
    This post is deleted!

  • 0

    :D...I've seen it in email. You are right, I've delete two rows of code of deleting node to get faster performance. Thanks for your reply~


Log in to reply
 

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