[数据结构与算法]102. 二叉树的层序遍历 队列实现BFS

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

思路

将每层的结点压入队列，记录下压入的数量，然后遍历这么多数量的结点（队列保证了先进先出），将这些结点的值存入二维数组中，i层放在result[i-1]，vector自带的push_back可以很轻松的实现这种操作，同时将这些结点的子节点压入队列。当队列为空时结束操作

class Solution {
public:
	//作为存储结点的队列
    queue<TreeNode*> ans;
    //存储结果的二维数组
    vector<vector<int>> result;
    
    void BFS(int layer,int size)
    {
    	//暂时存储队列中弹出的元素
        vector<int> temp;
        //k记录此次压入队列中的元素的个数
        int k=0;
        
        //遍历队列中存储的上一层的结点
        for(int i=0;i<size;i++)
        {
        	//取出队列的第一个元素，并弹出第一个元素，再将其值放入temp中
            auto p=ans.front();
            ans.pop();
            temp.push_back(p->val);

			//左右孩子结点不为空就压入队列，并且计数器加1
            if(p->left!=nullptr)
            {
                ans.push(p->left);
                k++;
            }
            if(p->right!=nullptr)
            {
                ans.push(p->right);
                k++;
            }
            
        }
        //将temp中的元素存入数组result中
        result.push_back(temp);
        //如果这次有元素压入队列，则再次调用BFS，直到没有新的元素压入队列位置
        if(k!=0)
        {
            BFS(layer+1,k);
        }
    }

    vector<vector<int>> levelOrder(TreeNode* root) {
    	//判断根节点的是否为空，不为空压入，否则直接输出
        if(root)
        {
            ans.push(root);
        }else
        {
            return result;
        }
        //调用函数，有两个参数，第一个参数是对应当前树的层数，第二个参数对应队列数据的个数
        BFS(0,1);
        return result;
    }
};