1 定义
广度优先搜索 （Breadth First Search），又叫层次遍历或宽度优先搜索，通常是以二叉树或图作为研究对象，先从上往下对该二叉树的每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完当前层才进入下一层，直到没有结点可以访问为止。
2 例题
【leetcode-102】给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
3 解决方法
3.1 双数组
3.1.1 大致思路
创建两个vector，分别为cur和next，其中cur含有当前访问层中的所包含的节点，next含有cur（极next的上一层）的各个节点的左右子节点，创建一个数组vals用来储存各个节点的值。遍历cur中的每个节点，将其每个节点的子节点放入next中，如果是nullptr就不放（这样的话，直到该二叉树的最后一层，将不再有子节点，也可以成为循环的符合条件），同时，将cur中的每个节点的节点值放到vals中，遍历结束后将cur替换成next就可以才是下一轮的遍历了，知道cur中不再有节点为止。
3.1.2 具体步骤
1 声明一个cur的数组，并使其初始化含有root节点；
2 以cur数组中存在节点为条件，开始外层循环；
3 声明一个数组vals用来储存cur数组个各个节点的值；
4 声明一个数组next以从左到右（或从右到左）的顺序，来储存cur的子节点；
5 开始内层循环用来将cur数组中的节点的值放入vals中，并且将cur中的各个子节点的存放到next中；
6 离开内层循环（仍在外层循环内），开始善后工作:将vals放入ans内,将cur数组用next来替换
3.1.3 代码
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if(root == nullptr){ //考虑root不存在的极端情况
return {};
}
vector<vector<int>> ans; //声明最后返回的答案
vector<TreeNode*> cur = {root};
while(cur.size()){
vector<int> vals;
vector<TreeNode*> next;
for(auto node:cur){
vals.push_back(node->val);
if(node->left){
next.push_back(node->left);
}
if(node->right){
next.push_back(node->right);
}
}
cur = move(next);
ans.emplace_back(vals);
}
return ans;
}
};3.2 单队列
3.2.1 大致思路
利用队列这个数据结构（先进先出）的特性，将root节点放入队列中去，然后将其值赋个用来储存各个节点值的vals数组中，然后将该节点的各个子节点再放入相同的队列（即自己这个节点的后面），如此循环。
3.2.2 具体步骤
1 声明答案ans，一个存放节点的队列q，并将root节点放到q中去；
2 以队列q不是空的作为循环条件，开启外层循环用来依次存放当前层的节点；
3 声明一个用来储存各节点值的数组vals；
4 以队列中仍有节点为循环条件，开启内层循环用来遍历当前层的节点；
5 内层循环中，声明一个暂时的变量用来存放队列头部的节点；
6 存放完成后弹出头节点，并将头节点的值存放入vals中；
7 检查当前节点是否有子节点，如有，将其子节点放入队列
8 跳出内层循环（仍在外层循环中），将vals存放入ans中
3.2.3 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if(root == nullptr){ //考虑root不存在的极端情况
return {};
}
vector<vector<int>> ans; //声明答案ans，一个存放节点的队列q，并将root节点放到q中去；
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){ //以队列q不是空的作为循环条件，开启外层循环用来依次存放当前层的节点；
vector<int> vals; //声明一个用来储存各节点值的数组vals；
for(int n = q.size();n--;){ //以队列中仍有节点为循环条件，开启内层循环用来遍历当前层的节点；
auto node = q.front(); //内层循环中，声明一个暂时的变量用来存放队列头部的节点；
q.pop(); //存放完成后弹出头节点，并将头节点的值存放入vals中；
vals.push_back(node->val);
if(node->left){ //检查当前节点是否有子节点，如有，将其子节点放入队列
q.push(node->left);
}
if(node->right){
q.push(node->right);
}
}
ans.emplace_back(vals); //跳出内层循环（仍在外层循环中），将vals存放入ans中
}
return ans;
}
};
