BFS简介

BFS（Breadth First Search）：宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

代码模板

我们利用一个辅助队列来存储每一层的结点。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
	vector<int>temp; //存放每一层结点的数组
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > ans;
        if(!pRoot) return ans;
        queue<TreeNode *>q;
        q.push(pRoot);
        while(!q.empty())
        {
        	int s = q.size();
        	for(int i = 0;i<s;++i) //开始遍历每一层的结点
        	{
        		TreeNode *t = q.front();
        		q.pop();
        		if(t->left) q.push(t->left);
        		if(t->right) q.push(t->right);
        		temp.push_back(t->val);
        	}
        	ans.push_back(temp);
        	temp.clear(); //把数组清空用于存储下一层结点
        }
        return ans;
    }
    
};