广度优先搜索BFS（二）

　　题目102。二叉树的层次遍历
　　题意：输入一棵二叉树，需要将树的每一层从左到右存入到vector中，然后每一次按照树的顺序从上往下排。
　　思路：可以使用BFS来进行遍历整棵二叉树，BFS遍历刚好是从左到右，从上到下一层层往下遍历；可以记录每一层的个数，等遍历完一层后再记录下一层的个数。
　　使用题目上的例子为例：
　　创建一个队列和vectorvectorint容器，变量nCount代表当前层的个数。
　　先将根节点放入队列，根节点当前层数是nCount1；将根节点3出队列，遍历3的左右子节点，都不为空，加进队列，将3也放入vector容器；判断nCount是否等于0，如果是0，就证明当前层已经遍历完，将nCount更新为队列里节点的个数nCount2，为下一层节点的个数，vector容器创建新的，存储下一层的数据；
　　节点9出队列，遍历节点9的左右子节点，都为空，nCount1，vector存储9；节点20出队列，左右节点都不为空，进入队列，nCount0，vector存储20；nCount为0，将nCount赋值为队列的节点个数，vector容器创建新的；
　　节点15出队列，左右节点为空，nCount1，vector存储15；节点7出队列，左右节点为空，nCount0，vecto存储7；
　　以上所示就完成二叉树层的遍历。
　　代码：classSolution｛public：vectorvectorintlevelOrder（TreeNoderoot）｛vectorvectorintvResult；queueTreeNodeq；q。push（root）；intnCount1；vectorintvLayer；while（！q。empty（））｛TreeNodecurnodeq。front（）；q。pop（）；nCount；if（curnode！nullptr）｛vLayer。pushback（curnodeval）；q。push（curnodeleft）；q。push（curnoderight）；｝if（nCount0）｛if（vLayer。size（）！0）｛vResult。pushback（vLayer）；｝vLayer。clear（）；nCountq。size（）；｝｝returnvResult；｝｝；
　　题目117。填充每个节点的下一个右侧节点指针
　　题意：给定一棵二叉树，每个节点有左右子节点还有一个next指向的节点，其中next指针指向当前节点右边的节点，如果当前右边没有节点就指向NULL。
　　思路：其实思路跟上一题差不多，也是使用BFS遍历整棵二叉树，每一层遍历，子节点进入队列的顺序是左子节点先入，后入右子节点，这样就可以节点出队列，节点next指针就直接指向队列的下一个节点，每当当前层遍历完就指向NULL。
　　使用题目的例子为例
　　创建一个队列和变量nCount，队列用来存储遍历的节点，nCount来记录当前层的节点数。
　　先将根节点1加进队列，nCount1，代表当前层只有一个节点；根节点1出队列，遍历左右子节点，都不为空，将左子节点2进入队列，右子节点3进入队，nCount0；当nCount0代表当前层已经遍历完，节点1的next指针指向NULL，nCount赋值为队列节点的个数，nCount2，下一层节点数；
　　节点2出队列，遍历左右子节点，不为空，节点4进入队列，节点5进入队列，nCount1；nCount不为0，说明队列头节点是当前节点的右侧节点，当前节点next指针指向队列头节点3；节点3出队列，右节点7不为空，进入队列，nCount0；nCount为0，当前层遍历完，nCount赋值为队列节点个数，nCount3，当前节点3的next指针指向NULL；
　　接下的流程跟上述一样，节点出队列，判断nCount是否为0，如果不是0，当前节点的next指向队列头节点，如果是0，当前节点的next指向NULL，当前层遍历完，nCount赋值队列节点个数，直到队列为空。
　　代码：classSolution｛public：Nodeconnect（Noderoot）｛if（rootnullptr）｛returnnullptr；｝queueNodeq；q。push（root）；intnCountq。size（）；while（！q。empty（））｛Nodetopq。front（）；q。pop（）；nCount；if（topleft！nullptr）｛q。push（topleft）；｝if（topright！nullptr）｛q。push（topright）；｝if（nCount0）｛Nodenextq。front（）；topnextnext；｝else｛topnextnullptr；nCountq。size（）；｝｝returnroot；｝｝；