广度优先搜索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;
    }
};