O(1) space, O(N) time

  • 0

    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.