단순 반복 + 레이어 반복 (레이어 기록) 116.각 노드의 다음 오른쪽 노드 포인터 117을 채웁니다.각 노드의 다음 오른쪽 노드 포인터 채우기 II

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    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) return root;
        root->next=NULL;
        getnext(root->left,root->right);
        return root;
    }
private:
    void getnext(Node* a,Node * b){
        if(!a||!b) return;
        a->next=b;
        getnext(a->left,a->right);
        getnext(a->right,b->left);
        getnext(b->left,b->right);
        return;
    } 
};

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    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) return root;
        Q.push(root);
        Node * end=root;
        Node * cur;
        Node * pre=end;
        while(!Q.empty()){
            Node* tmp=Q.front();
            Q.pop();
            if(tmp->left){
                Q.push(tmp->left);
                cur=tmp->left;
            }
            if(tmp->right){
                Q.push(tmp->right);
                cur=tmp->right;
            }

            if(tmp==end) {
                if(pre)
                pre->next=tmp;
                tmp->next=NULL;
                end=cur;
                pre=NULL;
            }
            else {
            if(pre)
            pre->next=tmp;
            pre=tmp; 
            }
        }
        return root;
    }
private:
    queue<Node* > Q;
};

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return root;
        Q.push(root);
        Node *tmp;
        Node *pre=NULL;
        while(!Q.empty()){
            int size=Q.size();
            while(size--){
            tmp=Q.front();
            Q.pop();
            if(pre) pre->next=tmp;
            if(!size) tmp->next=NULL;
            if(tmp->left)
            Q.push(tmp->left);
            if(tmp->right)
            Q.push(tmp->right);
            pre=tmp;
            }
            pre=NULL;
        }
        return root;
    }
private:
    queue<Node* > Q;
};

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return root;
        Q.push(root);
        Node *tmp;
        while(!Q.empty()){
           int size=Q.size();
           while(size--){
           tmp=Q.front();
           Q.pop();
           if(size) tmp->next=Q.front();
           else tmp->next=NULL;
           if(tmp->left) Q.push(tmp->left);
           if(tmp->right) Q.push(tmp->right);
           }
        }
        return root;
    }
private:
    queue<Node* > Q;
};