Where did I get wrong? JAVA.


  • 3
    R

    I understand the code doesn't look concise or pretty. However, it pases 34/61 cases. And I'm not sure where is the problem. Since there are cases before No.34 that has several nodes.next() has no child, and the code passed those cases. I don't know how could it miss those two 8s in this case.

    Any help would be appreciated.

    34 / 61 test cases passed.
    Status: Wrong Answer
    Submitted: 14 minutes ago
    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,#}

       /**
     * Definition for binary tree with next pointer.
     * public class TreeLinkNode {
     *     int val;
     *     TreeLinkNode left, right, next;
     *     TreeLinkNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public void connect(TreeLinkNode root) {
            if(root==null||(root.left==null&&root.right==null)) return;
            
            if(root.left!=null){                                                            //root.left!=null
                if(root.right!=null){                                                           //root.left&right!=null     left->right
                root.left.next=root.right;
                if(root.next==null) root.right.next=null;
                else{                                                                           //root.left!=null,right==null left->next.left/right
                    TreeLinkNode temp=root;
                    while(temp.next.next!=null) {                                               //while loop to skip the next() that has no child
                        if(temp.next.left==null&&temp.next.right==null) temp=temp.next;
                        else break;
                    }
                        if(temp.next.left==null&&temp.next.right==null) root.right.next=null;
                        else{
                            if(temp.next.left!=null) root.right.next=temp.next.left;
                            else root.right.next=temp.next.right;
                        }
                }
                }else{                                                                      //Same for root.left!=null + root.right==null
                    if(root.next==null) root.left.next=null;
                    else{
                        TreeLinkNode temp=root;
                        while(temp.next.next!=null) {if(temp.next.left==null&&temp.next.right==null) temp=temp.next; else break;}
                        if(temp.next.left==null&&temp.next.right==null) root.left.next=null;
                        else{
                            if(temp.next.left!=null) root.left.next=temp.next.left;
                            else root.left.next=temp.next.right;
                        }
                    }
                }
            }else{                                                                          //Same procedure for root.left==null, root.right!=null
                if(root.next==null) root.right.next=null;
                else{
                    TreeLinkNode temp=root;
                    while(temp.next.next!=null) {if(temp.next.left==null&&temp.next.right==null) temp=temp.next; else break;}
                        if(temp.next.left==null&&temp.next.right==null) root.right.next=null;
                        else{
                            if(temp.next.left!=null) root.right.next=temp.next.left;
                            else root.right.next=temp.next.right;
                        }
                }
            }
            connect(root.left);                                                             //Continue moving nodes downward.
            connect(root.right);
            return;
        }
    }

  • 1
    A

    Hi,

    I am facing similar issue at same test case. Did u happen to find the issue here? And also can you please tell me how will the tree look like for input: {2,1,3,0,7,9,1,2,#,1,0,#,#,8,8,#,#,#,#,7}. Thanks.


  • 0
    R

    Yes, I worked out the issue here. There are several border cases that I did not consider carefully.

    How the tree look like in LeetCode, for this question, it has deliberate explanation under each question. I'm sure you can find the link.
    I can give you the example here. For the input you mentioned, the tree should be

    2

    1 3

    0 7 9 1

    2 # 1 0 # # 8 8

    #, ( ), # #, 7, (.........)


Log in to reply
 

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