一个二叉树，树中每个节点的权值互不相同。
现在给出它的后序遍历和中序遍历，请你输出它的层序遍历。
输入格式
第一行包含整数 N，表示二叉树的节点数。
第二行包含 N 个整数，表示二叉树的后序遍历。
第三行包含 N 个整数，表示二叉树的中序遍历。
输出格式
输出一行 N 个整数，表示二叉树的层序遍历。
数据范围
1≤N≤30
官方并未给出各节点权值的取值范围，为方便起见，在本网站范围取为 1∼N。
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2
以这个问题为例，这道题的思路很明显就是先建立这个二叉树，如何广搜搜一遍就是层次遍历
那如何建树呢？
其实只要给出任意两种遍历方式就能建树，这里我们以这个题为例，请往下看：
前序：根左右，中序：左根右，后序：左右根（这个一定要牢记）
从后序的根节点入手，去定位到中序的根，然后进入左子树（如果存在），在进入右子树，不断的递归，每一次都用hash表记录根的左右节点的值，建立这颗树，当然在下面的代码部分我会解释一些技巧，然后bfs去一层一层遍历树就行了
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 35;
int bck[N],mid[N];
unordered_map<int,int> l,r,m;
int n;
int build(int mid_l,int mid_r,int bck_l,int bck_r){
int root = bck[bck_r];
int index = m[root];
if(mid_l < index) l[root] = build(mid_l,index - 1,bck_l,bck_l + index - mid_l - 1);
if(mid_r > index) r[root] = build(index + 1,mid_r,bck_r + index - mid_r,bck_r - 1);
return root;
}
void bfs(int root){
queue<int> q;
q.push(root);
while(!q.empty()){
auto ans = q.front();
cout << ans << " ";
q.pop();
if(l[ans]) q.push(l[ans]);
if(r[ans]) q.push(r[ans]);
}
}
int main()
{
cin >> n;
for(int i=0;i<n;i++) cin >> bck[i];
for(int i=0;i<n;i++){
cin >> mid[i];
m[mid[i]] = i;
}
int root = build(0,n-1,0,n-1);
bfs(root);
return 0;
}
这里是最难想的部分，一步一步来，如果左子树存在，那么找中序中左子树的左右端点，这个没有难度，但后序的左右端点就需要技巧了，首先左端点就是后序的左端点，右端点请看：
解方程式：设右端点是x，那么x - bck_l = index - 1 - mid_l,是不是有点懵这个地方为什么相等？
因为每次递归中序的右端点 - 左端点 == 后序的右端点 - 左端点，无论是左子树还是右子树
然后每次都根节点指向的都存到hash表里面
之后就是经典的bfs了，如果不懂bfs可以看看洛谷P1443 马的遍历（bfs广搜的基本应用）-CSDN博客
这道题还是比较经典的，希望还是花时间啃一啃
加油
