最近刷到了一道题需要结合二叉树的层序遍历和使用中序和后序遍历构造二叉树。这类题型作为树的常见题型，有必要写博客记录一下。
先给出题目： 题目链接 102. Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example: Given binary tree [3,9,20,null,null,15,7],
3/ 9 20 / 15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ] 解题思路：二叉树的遍历有四种方式，前三种前序，中序，后序遍历使用dfs实现，而层序遍历使用bfs实现。不了解bfs的小伙伴可以先去百度一下。 bfs（广度优先搜索）的思路是在找到可以达到的一步后，搜索以当前点为支点，搜索所有可以一步到达的下一点，直到找到目标或者退出搜索。使用队列实现。、 而层序遍历则是把每一层作为支点，搜索从当前层出发，所有可以到达的下一层。 代码如下：
class Solution { public: vector<vector<int>> ans; queue<TreeNode*> q; //使用队列模拟 vector<vector<int>> levelOrder(TreeNode* root) { TreeNode* head; if(root)q.push(root); { int cnt = 1;// cnt记录当前层儿子的数量 while(!q.empty()) { int temp = 0; vector<int> num; for(int i = 0; i < cnt; i++) { head = q.front(); num.push_back(head->val); if(head->left) { q.push(head->left); temp++; } if(head->right) { q.push(head->right); temp++;} q.pop(); } ans.push_back(num); cnt = temp; } } return ans; }