引言

二叉树，历来是C/C++软件工程师面试必备内容，之所以如此受欢迎，主要是因为二叉树的考查可易可难，企业可以根据考查重点，应聘者的水平要求方面来出题，而且都是二叉树方面的东西；另外，通过二叉树的考查，也可以看出应聘者对于数据结构、代码优化能力等方面的水平。

本节将介绍二叉树的另一个考点——二叉树的层序遍历

需求介绍：给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},

二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]

]

提示:0 <= 二叉树的结点数 <= 1500

测试样例如下：

示例1

输入：

{1,2}

返回值：

[[1],[2]]

示例2

输入：

{1,2,3,4,#,#,5}

返回值：

[[1],[2,3],[4,5]]

代码设计思路：该代码可以通过队列来实现，既然是层序遍历，说明整个遍历过程只需要从根节点开始，然后下一层从左到右的进行输出即可。

示例代码如下：

vector<vector<int> > levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode *> q;
        if (nullptr == root)
        {
            return res;
        }
        q.push(root);
        while (!q.empty())
        {
            vector<int> tmp;
            int n = q.size();
            for (int i = 0; i < n; i++)
            {
                TreeNode *node = q.front();
                q.pop();
                tmp.push_back(node->val);
                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
            }
            res.push_back(tmp);
        }
        return res;
        }

结语

想要得到一个二叉树的层序遍历结果并不难，关键是想清楚用什么方式来实现，而通过队列来实现二叉树的遍历输出，无疑是一个较为简介的方式。

当然，通过BFS迭代的方式也能够很快得出相关结果，一下是设计思路：
主要思路：广度优先
如下图所示：一层一层地遍历二叉树，
1、遍历到一个节点，将左右个孩子加入队列；
2、一次遍历二叉树的一层；
3、怎么确定能遍历一层：每次遍历队列，先记录队列的大小size，出队size次，这些值即为一层，存入res数组，并通过1、2将下一层的节点存入队列；