题目链接:树的遍历
详细见代码:
#include<bits/stdc++.h>
using namespace std;
const int N=35;
int postorder[N],inorder[N],pos[N];//pos[i]记录中序遍历中值 为i 的数对应的在中序遍历中的位置
vector<int>level[N];//记录层序遍历的顺序
void build(int pl,int pr,int il,int ir,int d){//pl,pr,il,ir分别表示在后序遍历以及中序遍历中对应的起点和终点,d表示递归建立到第d层
if(pl>pr) return;
int val=postorder[pr];//val为此层的根节点的值
level[d].push_back(val);
int k=pos[val];//值为val的值在中序遍历中对应的位置
build(pl,pl+k-1-il,il,k-1,d+1);//递归建立左子树 ;此时后序遍历的终点x, x-pl=k-1-il,该式子表示在后序、中序遍历中对应的长度相同
build(pl+k-il,pr-1,k+1,ir,d+1); //递归建立右子树
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>postorder[i];
}
for(int i=0;i<n;i++){
cin>>inorder[i];
pos[inorder[i]]=i;
}
build(0,n-1,0,n-1,0);
for(int i=0;i<n;i++){
for(int x:level[i]) cout<<x<<' ';
}
}