Can anyone explain why given test case fails in my solution?


  • 0
    H

    Here is the test case which fails
    Input: {3,9,20,#,#,15,7}
    Output: {3,#,9,20,#,15,#}
    Expected: {3,#,9,20,#,15,7,#}

    I can not understand expected output format. plz help

      void connect(TreeLinkNode *root) {
        if(!root) return;
        TreeLinkNode *p=root,*q;
        while(p->left)
        {
            q=p->left;
            while(p)
            {
                if(p->left && p->right) p->left->next=p->right;
                if(p->next)
                {
                    if(p->right)
                    {
                        if(p->next->left) p->right->next=p->next->left;
                        else    p->right->next=p->next->right;  
                    }    
                    else if (p->left && !p->right)
                    {
                        if(p->next->left) p->left->next=p->next->left;
                        else    p->left->next=p->next->right;  
                    }
                }
                p=p->next;
            }
            p=q;
        }
        
    }

  • 0
    D

    The output format is kind of by-level linked list format. Levels are separated by '#'. Or you can consider '#' as NULL. Take the input [3,9,20,#,#,15,7] as an example. The initial tree structure is like the following:

                  3
                /    \
              9       20
                     /   \  
                  15      7
    

    After connecting next pointer, the tree structure should be like this:

                  3
                /    \
              9 -->   20
                     /   \  
                  15  -->  7
    

    1st level: 3 --> NULL (#)

    2nd level: 9 --> 20 --> NULL (#)

    3rd level: 15 --> 7 --> NULL (#)

    Putting together, the by-level structure is : [3, #, 9, 20, #, 15, 7, #]

    The input binary tree is not full binary tree as in I. The issue in your code is that you didn't handle this correctly. The code starts level 3 with node 9. Since it has no children, your code just quits. Thus 15 and 7 are not connected.


Log in to reply
 

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