Java iterative solution with comments


  • 0
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null) return root;
        TreeNode dummyhead = new TreeNode(0);
        TreeNode paren = dummyhead;
        TreeNode curr = root;
        paren.left = curr;//Set dummyhead.left = real head.
        while(curr!=null&&curr.val!=key){
            paren = curr;
            if(curr.val<key){
                curr = curr.right;
            }
            else{
                curr = curr.left;
            }
        }
        if(curr == null) return root; //cannot find a root with root.val = key
        if(paren.left!=null&&paren.left.val==curr.val){
            if(curr.left!=null){  //Always push up the left child if there is any, or push up the right child
                paren.left = curr.left;
                TreeNode newRight = curr.left.right;
                if(newRight==null) curr.left.right = curr.right;
                else{
                    while(newRight.right!=null){
                        newRight = newRight.right;
                    }
                    newRight.right = curr.right;
                }
            }
            else{
                if(curr.right!=null){
                    paren.left=curr.right;
                }
                else paren.left = null;
            }
        }
        else if(paren.right!=null&&paren.right.val==curr.val){//just change "left" to "right" from above
            if(curr.left!=null){
                paren.right = curr.left;
                TreeNode newRight = curr.left.right;
                if(newRight==null) curr.left.right = curr.right;
                else{
                    while(newRight.right!=null){
                        newRight = newRight.right;
                    }
                    newRight.right = curr.right;
                }
            }
            else{
                if(curr.right!=null){
                    paren.right=curr.right;
                }
                else paren.right = null;
            }
        }
        else{
            
        }
        return dummyhead.left;
    }

Log in to reply
 

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