My recursive solution


  • 7
    J
    void connect(TreeLinkNode *root) {
        if( root == NULL || root->left == NULL && root->right == NULL )        //{} \ {0}
        {
           return;
        }
        
        TreeLinkNode *p, *q;
        p = root->left;
        q = root->right;
        p->next = q;
        while( p->right != NULL )
        {
            p = p->right;
            q = q->left;
            p->next = q;
        }
        
        connect( root->left );
        connect( root->right );
    }

  • 0
    R

    not clear about your recursive code, could you explain how do you divide the original problem into 2 sub problem?


  • 0
    J
    This post is deleted!

  • 0
    J

    Sorry I can not drow a tree here, it's a little difficult to show you. I write my method in my blog. Hope it can help you.
    Here is the link: https://wangxj.blog.ustc.edu.cn/?p=31


  • 3
    S

    The code looks okay. However, it uses extra current stack memory. You may want to go on to consider a pure iterative solution which uses constant memory.


  • 0
    R

    I know you meaning, your recursive seems elegant, but it is only suitable for perfect BT, what if not, it may be incorrect....


  • 0
    S

    If the input tree is just a single node then its next has to be set as NULL.
    But in your code, it doesn't happen as the first return statement will be executed.
    However your code was accepted, when I submitted.
    Please correct me if I am wrong.
    Thanks in advance


  • 0
    J

    Yes, you can set the root->next to NULL if there is just a single node. I think my code was accept because all the next of the nodes are NULL as default. So you didn't have to reset it to NULL.


  • 0
    S

    Ohh yes. I forget the initial status of next ptr. Thanks for the reply @jwang8


  • 0
    A
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the FAQ for more info. Take a look at good sharing example


Log in to reply
 

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