广度优先搜索BFS（二）

　　题目102.二叉树的层次遍历
　　题意：输入一棵二叉树，需要将树的每一层从左到右存入到vector中，然后每一次按照树的顺序从上往下排。
　　思路：可以使用BFS来进行遍历整棵二叉树，BFS遍历刚好是从左到右，从上到下一层层往下遍历；可以记录每一层的个数，等遍历完一层后再记录下一层的个数。
　　使用题目上的例子为例：
　　创建一个队列和vector>容器，变量nCount代表当前层的个数。
　　先将根节点放入队列，根节点当前层数是nCount=1；将根节点3出队列，遍历3的左右子节点，都不为空，加进队列，将3也放入vector容器；判断nCount是否等于0，如果是0，就证明当前层已经遍历完，将nCount更新为队列里节点的个数nCount=2，为下一层节点的个数，vector容器创建新的，存储下一层的数据；
　　节点9出队列，遍历节点9的左右子节点，都为空，nCount=1，vector存储9；节点20出队列，左右节点都不为空，进入队列，nCount=0，vector存储20；nCount为0，将nCount赋值为队列的节点个数，vector容器创建新的；
　　节点15出队列，左右节点为空，nCount=1，vector存储15；节点7出队列，左右节点为空，nCount=0，vecto存储7；
　　以上所示就完成二叉树层的遍历。
　　代码： class Solution { public:     vector> levelOrder(TreeNode* root) {         vector< vector > vResult;         queue q;         q.push(root);         int nCount = 1;         vector vLayer;         while(!q.empty()) {             TreeNode* curnode = q.front();             q.pop();             nCount--;              if(curnode != nullptr) {                 vLayer.push_back(curnode->val);                 q.push(curnode->left);                 q.push(curnode->right);             }             if(nCount == 0) {                 if(vLayer.size() != 0) {                     vResult.push_back(vLayer);                 }                 vLayer.clear();                 nCount = q.size();             }         }         return vResult;     } };
　　题目117.填充每个节点的下一个右侧节点指针||
　　题意：给定一棵二叉树，每个节点有左右子节点还有一个next指向的节点，其中next指针指向当前节点右边的节点，如果当前右边没有节点就指向NULL。
　　思路：其实思路跟上一题差不多，也是使用BFS遍历整棵二叉树，每一层遍历，子节点进入队列的顺序是左子节点先入，后入右子节点，这样就可以节点出队列，节点next指针就直接指向队列的下一个节点，每当当前层遍历完就指向NULL。
　　使用题目的例子为例
　　创建一个队列和变量nCount，队列用来存储遍历的节点，nCount来记录当前层的节点数。
　　先将根节点1加进队列，nCount=1，代表当前层只有一个节点；根节点1出队列，遍历左右子节点，都不为空，将左子节点2进入队列，右子节点3进入队，nCount=0；当nCount=0代表当前层已经遍历完，节点1的next指针指向NULL，nCount赋值为队列节点的个数，nCount=2，下一层节点数；
　　节点2出队列，遍历左右子节点，不为空，节点4进入队列，节点5进入队列，nCount=1；nCount不为0，说明队列头节点是当前节点的右侧节点，当前节点next指针指向队列头节点3；节点3出队列，右节点7不为空，进入队列，nCount=0；nCount为0，当前层遍历完，nCount赋值为队列节点个数，nCount=3，当前节点3的next指针指向NULL；
　　接下的流程跟上述一样，节点出队列，判断nCount是否为0，如果不是0，当前节点的next指向队列头节点，如果是0，当前节点的next指向NULL，当前层遍历完，nCount赋值队列节点个数，直到队列为空。
　　代码： class Solution { public:     Node* connect(Node* root) {         if(root == nullptr) {             return nullptr;         }         queue q;         q.push(root);         int nCount = q.size();         while(!q.empty()) {             Node* top = q.front();             q.pop();             nCount--;             if(top->left != nullptr) {                 q.push(top->left);             }             if(top->right != nullptr) {                 q.push(top->right);             }             if(nCount > 0) {                 Node *next = q.front();                 top->next = next;             }             else {                 top->next = nullptr;                 nCount = q.size();             }         }         return root;     } };