Simple 40ms c++ o(n) ,o(1) solution with only one while loop


  • 35
    A

    Thanks for liji94188 for adding the explanation:

    It's a BFS traversal. now pointer is the current level traveler and head is the left most element at next level and the tail is the right most element at next level till now. We move now pointer at current level and populate the the next-link at its children level. (Here the gist is we can move now to its next because this relationship was already populated in the previous round).

    void connect(TreeLinkNode *root) {
        TreeLinkNode *now, *tail, *head;
        
        now = root;
        head = tail = NULL;
        while(now)
        {
            if (now->left)
                if (tail) tail = tail->next =now->left;
                else head = tail = now->left;
            if (now->right)
                if (tail) tail = tail->next =now->right;
                else head = tail = now->right;
            if(!(now = now->next))
            {
                now = head;
                head = tail=NULL;
            }
        }
    }

  • 0
    O
    if(!(now = now->next))
    

    What are you check here?


  • 1
    A

    I am checking if now->next is empty
    And at the same time move now to now->next

    It run now=now ->next first and then return now


  • 0
    B
    This post is deleted!

  • 0
    R

    where is the explanations then?


  • 0
    L

    Hi rabeeh, It's a BFS traversal. now pointer is the current level traveler and head is the left most element at next level and the tail is the right most element at next level till now. We move now pointer at current level and populate the the next-link at its children level. (Here the gist is we can move now to its next because this relationship was already populated in the previous round).


  • 3
    L

    It's a BFS traversal. now pointer is the current level traveler and head is the left most element at next level and the tail is the right most element at next level till now. We move now pointer at current level and populate the the next-link at its children level. (Here the gist is we can move now to its next because this relationship was already populated in the previous round).


  • 0
    A

    Thanks! That is an excellent job explaining it.


  • 0
    L

    Hi aileengw, it was me who to say thank you for sharing such cool solution :)


  • 0
    A

    No problem :)


Log in to reply
 

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