Anyone helps to find bug for my code?


  • 0
    C

    here is my code, the system says my code is wrong answer:
    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,#}
    I was stuck by this problem for 3 days and can't figure out where the problem is in my code.
    Any kinds of help will be appreciated!

    class Solution {
    public:
    void connect(TreeLinkNode *root) {
         if(root == NULL) return;
        TreeLinkNode *l = NULL, *r = NULL, *t = NULL;
        l = root->left;
        r = root->right;
        if(l)
        {
            if(r)
            {
                l->next = r;
                t = root->next;
                while(t)
                {
                    if((t->left==NULL)&&(t->right==NULL))
                    t = t->next;
                    else break;
                }
                
                if(t!=NULL)
                {
                    if(t->left!=NULL)
                    r->next = t->left;
                    else if(t->right!=NULL)
                    r->next = t->right;
                }
                else r->next = NULL;
            }
            else
            {
                t = root->next;
                if(t){
                while((t->left==NULL)&&(t->right==NULL))
                {
                    t = t->next;
                    if(!t) break;
    
                }
                }
                if(t!=NULL)
                {
                    if(t->left)
                    l->next = t->left;
                    else if(t->right)
                    l->next = t->right;
                }
                else
                l->next = NULL;
            }
        }
        else if(r)
        {
                t = root->next;
                if(t){
                while((t->left==NULL)&&(t->right==NULL))
                {
                    t = t->next;
                    if(!t) break;
                }
                
                }
            if(t!=NULL)
                {
                    if(t->left)
                    r->next = t->left;
                    else if(t->right)
                    r->next = t->right;
                }
            else
            r->next = NULL;
        }
        connect(root->left);
        connect(root->right);
    }
       };

  • 0
    S

    Could you please add comments in your code, and explain your algorithm? It is easy for others to understand your code and give help.


  • 8
    X

    in your code:
    connect(root->left);
    connect(root->right);

    which means you first recurs left sub-tree, then right subtree. The problem is the right subtree's next pointers are not processed. So in your example, 9->next should be 1, however, when you traverse the left sub tree, 9's next pointer is still NULL. Your code will think 9 is the end of the third level, so the fourth level's 0 will have its next to be NULL.

    Try change the recurs sequence as:
    connect(root->right);
    connect(root->left);


  • 0
    C

    thanks very much!


  • 0
    D

    thanks for your answer,it is a big help


Log in to reply
 

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