116. 填充每个节点的下一个右侧节点指针

/*
// 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:
    // 二叉树，递归
    // 层次遍历基于广度优先搜索，它与广度优先搜索的不同之处在于，广度优先搜索每次只会取出一个节点来拓展，而层次遍历会每次将队列中的所有元素都拿出来拓展，这样能保证每次从队列中拿出来遍历的元素都是属于同一层的，因此我们可以在遍历的过程中修改每个节点的next 指针，同时拓展下一层的新队列。
    Node* connect(Node* root) {
        if(root ==NULL){
            return root;
        }
        // 根节点不为空
        queue<Node*> q;
        q.push(root);
        while(q.size()){
            int size=q.size(); //记录当前队列中元素的个数
            for(int i=0;i<size;i++){
                auto t=q.front();
                q.pop();
                // 判断是否把这一层的结点连接在一起
                if(i<size-1){ // 最后一个结点不连接（所有next指针默认为NULL）
                    t->next=q.front();   // 当前弹出的结点指向队首结点(下一个将要弹出的元素)
                }
                // 扩展下一层的结点
                if(t->left!=NULL){  // 弹出一个结点时，也要把当前节点的左右子结点加入到队列中
                    q.push(t->left);   
                }
                if(t->right!=NULL){
                    q.push(t->right);
                }
              
            }
          
        }
        return root;
    }
};