O(1) space, O(N) time


  • 0
    H

    If we don't use queue (extra space), we need to remember the first node of the upper level so that we can traverse through the current level.

    void connect(TreeLinkNode *root) {
            if (!root) return;
            TreeLinkNode* parent = root;
            TreeLinkNode* first = root->left;
            TreeLinkNode* cur = first;
            while (cur) {
                while (parent) {
                    cur->next = parent->right;
                    cur = cur->next;
                    parent = parent->next;
                    if (parent) {
                        cur->next = parent->left;
                        cur = cur->next;
                    }
                }
                parent = first;
                cur = first->left;
                first = cur;
            }
        }

Log in to reply
 

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