Why my code can't pass this?


  • 0
    Y
         public void connect(TreeLinkNode root) {
                if(root==null ||(root.left==null&&root.right==null)) return;
                if(root.left!=null){
                    if(root.right!=null){
                        root.left.next = root.right;
                    }else{
                        root.left.next = findNext(root.next);
                    }
                }
                if(root.right!=null){
                    root.right.next = findNext(root.next);
                }
                connect(root.left);
                connect(root.right);
                return;
            }
            private TreeLinkNode findNext(TreeLinkNode root){
                if(root==null) return null;
                if(root.left!=null) return root.left;
                if(root.right!=null) return root.right;
                return findNext(root.next);
            }
    
    input:
    {2,1,3,0,7,9,1,2,#,1,0,#,#,8,8,#,#,#,#,7}
    Output:
    {2,#,1,3,#,0,7,9,1,#,2,1,0,#,7,#}
    Expected:
    {2,#,1,3,#,0,7,9,1,#,2,1,0,8,8,#,7,#}

  • 0
    Y

    I have the same problem with you, after a careful analysis, I found that this recursive solution has a problem: when you start to connect the child level, the nodes in parent level are not connect completely.

    In this bad case, you want to connect the node "0" in the forth level, but the node "9" in the third level is not connected to the node "1", so you miss the two "8"s


  • 0
    Y

    Thanks, it really took me a while to figure that out.


Log in to reply
 

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