C++ 13 lines iterative solution using queue, works for both cases


  • 0
    B
    class Solution {
    public:
        void connect(TreeLinkNode *root) 
        {
            if(!root) return;
            queue<TreeLinkNode*> q;
            q.push(root);
            q.push(NULL);
            TreeLinkNode* prev = NULL;
            while(q.size()>1)
            {
                if(q.front()==NULL) q.pop(), q.push(NULL), prev = NULL;
                TreeLinkNode* temp = q.front();
                q.pop();
                if(temp->left) q.push(temp->left);
                if(temp->right) q.push(temp->right);
                if(prev) prev -> next = temp;
                prev = temp;
            }
        }
    };

  • 0
    D
    This post is deleted!

  • 0
    D

    @beetlecamera The note says "you may only use constant extra space"...


  • 0
    B

    @Doradus
    Thank you for the remind.
    I just posted a solution with constant space at here.
    With the help of next pointer, we can treat each level as linked list, so we only need a constant space for head node.


Log in to reply
 

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