BFS广度优先搜索模板

广度优先搜索，就是像水中涟漪一样像外扩散，要基于队列实现。同时在向外搜索的时候要标记已经搜索的元素。

模板一：节点一个一个地出栈，一颗子树一颗子树地入栈

//比较好的广度优先搜索模板
//一个节点一个节点地入队出队
void bfs(起始点){
    将起始点放入队列中;
    标记起点访问;
    while(如果队列不为空){
    	访问队列中队首的元素x;//这里一般是对元素进行处理
        删除队首元素;
        for(x 的所有相邻点){
            if(该点未被访问且合法){//合法很重要，点不能越界
        		将该点加入队列末尾
       			标记已经被加入队列;
            }
        }
    }
    队列为空，广搜结束; 
}     

模板二：节点一层一层入栈，一层一层出栈

//一层节点一层节点地入队出队
class Solution {
public:
    vector> levelOrder(Node* root) {
        if(!root)   return {};
        vector > ans;
        queue q;
        Node* p = root;
        q.push(root);
        int size = 0,nums = 0;
        while(!q.empty()){
            vector res;
            size = q.size();
            for(int i = 0;i < size;i++){//将一个层次的节点出栈
                p = q.front();
                q.pop();///出栈
                res.push_back(p->val);
                nums = p->children.size();
                for(int j = 0;j < nums;j++){//将下一个层次的节点入栈
                    q.push(p->children[j]);
                }
            }
            ans.push_back(res);
        }
        return ans;
    }
};