C++ solution using 2 queues


  • 0
    A
    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            if(!root)
                return;
            queue<TreeLinkNode*> q1, q2;
            q1.push(root);
            TreeLinkNode* curr1 = nullptr;
            TreeLinkNode* curr2 = nullptr;
            while(!q1.empty() || !q2.empty()) {
                while(!q1.empty()) {
                    curr1 = q1.front();
                    if(curr1->left)
                        q2.push(curr1->left);
                    if(curr1->right)
                        q2.push(curr1->right);
                    q1.pop();
                    curr2 = (!q1.empty()) ? q1.front() : nullptr;
                    curr1->next = curr2;
                    if(curr2)
                        curr2->next = nullptr;
                }
                while(!q2.empty()) {
                    curr1 = q2.front();
                    if(curr1->left)
                        q1.push(curr1->left);
                    if(curr1->right)
                        q1.push(curr1->right);
                    q2.pop();
                    curr2 = (!q2.empty()) ? q2.front() : nullptr;
                    curr1->next = curr2;
                    if(curr2)
                    curr2->next = nullptr;
                }
            }
        }
    };

Log in to reply
 

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