给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数N（<=30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2
分析
对于后序遍历序列 ： 最后一个值是根，前面一部分是左儿子 ， 中间一部分是右儿子。
比如样例 ： 4 是根 ， 231 是左儿子 ， 576 是右儿子。
如何找到哪一段是左儿子，哪一段是右儿子 ？
看中序遍历序列 ： 在中序遍历序列中找到根 4 。 它左边有3个数，全是它的左儿子。右边同理。
这样就找到左儿子是有三个数 ， 右儿子是有 3 个数的，这样看回后序遍历序列。就知道前三个数是左儿子，紧接着的3个数是右儿子。
就这样慢慢还原一棵树。然后bfs层序输出。
代码如下
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#define CLR(x) memset(x,0,sizeof(x))
#define LL long long
using namespace std;
int mid[50],hou[50];
struct node{
int l , r;
}a[50];
int build(int la,int ra,int lb,int rb){
if(la > ra) return 0;
int rt = hou[rb];
int p1 = la , p2 ;
while(mid[p1] != rt) p1++;
p2 = p1 - la;
a[rt].l = build(la,p1-1,lb,lb+p2-1);
a[rt].r = build(p1+1,ra,lb+p2,rb-1);
return rt;
}
void bfs(int x)
{
queue<int> q;
vector<int> g;
q.push(x);
while(!q.empty()){
int w = q.front();
q.pop();
if(w == 0) break;
g.push_back(w);
if(a[w].l != 0){
q.push(a[w].l);
}
if(a[w].r != 0){
q.push(a[w].r);
}
}
for(int i = 0 ; i < g.size() ; i++){
printf("%d%c",g[i],i==g.size()-1 ? '\n' : ' ');
}
return;
}
int main()
{
int n;
cin >> n;
for(int i = 0 ; i < n ; i++) cin >> hou[i];
for(int i = 0 ; i < n ; i++) cin >> mid[i];
build(0,n-1,0,n-1);
int root = hou[n-1];
bfs(root);
}
