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

思路：
BFS，层次遍历的时候，我用的Queue存储每层的所有元素，因此我先用Node* node保存Q的第一个元素，然后把Q的第一个pop掉，然后让node的next指向pop之后的Q的第一个元素，就顺理成章完成了本题！

BFS（题解的高效解法）

class Solution {
public:
    Node* connect(Node* root) {
        bfs(root);
        return root;
    }
    void bfs(Node* root){
        if(!root){
            return;
        }
        queue<Node*> qn;
        qn.push(root);
        while(!qn.empty()){
            int sz=qn.size();
            for(int i=0;i<sz;++i){
                Node* node=qn.front();
                qn.pop();
                if(node){
                    if(i<sz-1){
                        node->next=qn.front();
                    }
                    if(node->left){
                        qn.push(node->left);
                    }
                    if(node->right){
                        qn.push(node->right);
                    }
                }
            }

        }
    }
};

BFS（我的繁琐解法）

class Solution {
public:
    Node* connect(Node* root) {
        bfs(root);
        return root;
    }
    void bfs(Node* root){
        if(!root){
            return;
        }
        queue<Node*> qn;
        qn.push(root);
        while(!qn.empty()){
            int sz=qn.size();
            vector<Node*> v;
            for(int i=0;i<sz;i++){
                Node* node=qn.front();
                qn.pop();
                
                if(node){
                    if(node->left){
                        qn.push(node->left);
                        v.push_back(node->left);
                    }
                    if(node->right){
                        qn.push(node->right);
                        v.push_back(node->right);
                    }
                }

            }
            if(!v.empty()){
                for(int i=0;i<v.size()-1;++i){
                    v[i]->next=v[i+1];
                }
            }
        }
    }
};