Leetcode 117. 各ノードを充填する次の右側ノードポインタIIの解題構想とC++実現

方法一:層順遍歴
問題解決の考え方:
116番とそっくりですが、実はキューqueueのほうが簡単で、順番を逆さまにする必要はありません.キューの長さ情報queueを使用する.size()は、1つのキューだけで階層を巡ることができます.

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node() {}
    Node(int _val, Node* _left, Node* _right, Node* _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        if(root == NULL) return root;
        //    
        stack s1;
        s1.push(root);
        while(!s1.empty()){
            stack s2;
            Node* temp1 = NULL;
            Node* temp2 = NULL;
            while(!s1.empty()){
                temp1 = s1.top();
                s1.pop();
                temp1->next = temp2;
                temp2 = temp1;
                if(temp1->right)
                    s2.push(temp1->right);
                if(temp1->left)
                    s2.push(temp1->left);
            }
            //s2          
            while(!s2.empty()){
                s1.push(s2.top());
                s2.pop();
            }
        }
        return root;
    }
};