C++ 40ms O(1) space, O(N) time - simply assume next pointers are already populated at the current level


  • 2
    X

    The idea is merely the same as for the perfect binary tree case, with only the difference that before populating each next pointer we have to check whether it's not null, and if it is, iterate until one is encountered or the next tree level terminates. Anyway, the gist of this solution is to assume that next pointers at the current level are already populated, and hence we use them to traverse the current level and meanwhile populate the next pointers at the child level.

       void connect(TreeLinkNode *root) {
            TreeLinkNode* current = root;
            for(;;)
            {
                TreeLinkNode* p = current;
                TreeLinkNode* n = nullptr;
                // First find the first non-null node at the next level
                while(p)
                {
                    if(p->left)
                    {
                        n = p->left;
                        break;
                    }
                    if(p->right)
                    {
                        n = p->right;
                        break;
                    }
                    p = p->next;
                }
                if(n == nullptr)
                {
                    return; // no nodes at next level - everything already populated
                }
                // remember the first non-null node at the next level, since this is what the algorithm will start with 
                // on the next iteration
                TreeLinkNode* s = n;
                // now go ahead and populate next pointers with every non-null node, as if it's just a linked list
                if(n == p->left && p->right)
                {
                    n->next = p->right;
                    n = n->next;
                }
                p = p->next;
                while(p != nullptr)
                {
                    if(p->left != nullptr)
                    {
                        n->next = p->left;
                        n = n->next;
                    }
                    if(p->right != nullptr)
                    {
                        n->next = p->right;
                        n = n->next;
                    }
                    p = p->next;
                }
                current = s; // go next iteration
            }
        }

Log in to reply
 

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