题目描述
一个二叉树，树中每个节点的权值互不相同。
现在给出它的后序遍历和中序遍历，请你输出它的层序遍历。
输入描述
第一行包含整数 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
思路：
设置一个哈希表存左儿子，右儿子，和每个节点的位置，一共涉及两个函数，一个函数用来建立二叉树，一个函数用来遍历左右子树，这个题有一点需要注意的就是后序遍历的左右子的确定
关于build函数：传入中序遍历和后序遍历的左右边界，令根节点等于后序遍历的右边界，也就是最后一个数，k记录根节点的位置，分别对左右子树进行递归
关于bfs函数：这个函数让树先序输出出来，定义一个队列，将根节点存进去，q存在时候，弹出的队头节点输出，因为先序遍历是根左右，然后判断左右子树是否存在，如果存在，push到队列
代码样例
#include<iostream>
#include<map>
#include<bits/stdc++.h>
using namespace std;
#define N 50
map< int,int > l,r,mp;//mp记录数据的下标，l,r表示根的左右孩子
int inorder[N],order[N];//记录中序遍历和后序遍历
//参数是中序遍历的左端点右端点，后续遍历的左右端点
int creatTree(int il,int ir,int pl,int pr){
int k,root;
root=order[pr];//根节点是后序遍历的最后值
k=mp[root];//表示根节点对应的下标
//如果存在左子树，构造最左子树
if(il<k)
l[root]=creatTree(il,k-1,pl,k+pl-il-1);
//如果存在右子树，构造右子树
if(ir>k)
r[root]=creatTree(k+1,ir,pr+k-ir,pr-1);
return root;
}
void bfs(int root){
queue<int> p;
int t;
p.push(root);//将根节点放到队列
while(!p.empty()){
t=p.front();//把队列的首元素赋值给t
cout<<t<<" ";//输出t
p.pop();//删除队头元素
//判断节点是否存在左右节点
if(l[t])
p.push(l[t]);
if(r[t])
p.push(r[t]);
}
}
int main(){
int n,root;
cin>>n;
for(int i=0;i<n;i++)
cin>>order[i];
for(int i=0;i<n;i++){
cin>>inorder[i];
mp[inorder[i]]=i;
}
root=creatTree(0,n-1,0,n-1);//构建二叉树
bfs(root);//层序遍历
return 0;
}
这道题用到递归比较简单，它也能锻炼大家对树的理解，谢谢大家。
