【LeetCode题解】BFS层序遍历二叉树

【LeetCode题解】BFS层序遍历二叉树

102.二叉树的层序遍历

分析：

层序遍历，顾名思义，就是按一层一层的顺序来对二叉树进行遍历，遍历顺序如下图所示

那么如何对二叉树进行遍历呢，我们首先将上面二叉树各层按照遍历次序放在同一直线上

现在我们发现了这其实就是一个队列，我们可以利用队列元素先进先出的特点对二叉树进行层序遍历，下面是BFS遍历二叉树的算法：

//BFS遍历二叉树算法
void Bfs(TreeNode* root){
    queue queue;
    queue.push(root);		//根结点先进队列
    while(!queue.empty()){
        TreeNode* tempnode = queue.front(); //保存队头结点
        queue.pop();	//出队
        if(tempnode->left != nullptr){
            queue.push(tempnode->left);	//若刚刚出队的结点的左孩子不为空，则入队
        }
        if(tempnode->rught != nullptr){
            queue.push(tempnode->right)	//若刚刚出队的结点的右孩子不为空，则入队
        }
    }
}

来分析一下上面的算法：

1. 首先根结点入列，如图1-1，进入循环后先用tempnode将根结点保存，然后根结点出列，由于根结点的左孩子（二叉树中的2）不为nullptr，结点2入列，根结点的右孩子（二叉树中的3）不为nullptr，结点3入列，如图1-2。

2. 接着进入下一次循环，先用tempnode将结点2保存，然后结点2出列，由于结点2的左孩子（二叉树中的4）不为nullptr，结点4入列，结点2的右孩子（二叉树中的5）不为nullptr，结点5入列，如图1-3。

3. 就这样不断循环最终完成对二叉树的遍历。

到这里我们已经明白了BFS遍历二叉树的原理，但我们又面临一个问题，如上图1-3中，队列中的元素是3、4、5，这三个结点不在二叉树的同一层，也就是说BFS遍历二叉树的结果是一个一维数组，而层序遍历的结果要求是一个二维数组，如下图：

要对遍历的元素所在层数进行区分，我们就要知道该层元素的个数，然后将同一层的元素在一次循环中全部出列，相应的下一层元素全部入列，要做到这一点，我们在循环里面再嵌套一个循环即可。

BFS层序遍历二叉树完整C++代码如下：

class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        vector> res;
        queue queue;
        if(root != nullptr)
            queue.push(root);
        while(!queue.empty())
        {
            int n = queue.size();
            vector level;  // 用于储存同一层元素的信息
            for(int i = 0;i < n;i++)   //同一层元素全部出列，下一层元素全部入列
            {
                TreeNode* tempnode = queue.front();
                queue.pop();
                level.push_back(tempnode->val);
                if(tempnode->left != nullptr)
                    queue.push(tempnode->left);
                if(tempnode->right != nullptr)
                    queue.push(tempnode->right);
            }
            res.push_back(level);
        }
        return res;
    }
};