AcWing 1497. 树的遍历

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=40;
int postorder[N],inorder[N];
unordered_map<int,int> l,r;//用来记录每个点得左右子节点，因为没说从1到n
unordered_map<int,int> pos;//记录中序遍历得结点值所对应得位置
int build(int il,int ir,int pl,int pr){
    int root=postorder[pr];//后序遍历末尾是子树或树得根 
    int k=pos[root];//在中序遍历中的位置 
    if(il<k){
        l[root]=build(il,k-1,pl,pl+k-1-il);

    } 
    if(k<ir){
        r[root]=build(k+1,ir,pl+k-1-il+1,pr-1);
    }
    return root;//返回该点得根节点
}
int q[N];
int hh,tt;
void bfs(){
    q[tt]=postorder[n-1];
    while(hh<=tt){
        int t=q[hh++];
        if(l.count(t)){
            q[++tt]=l[t];
        }
        if(r.count(t)){
            q[++tt]=r[t];
        }
    }
    cout<<q[0];
    for(int i=1;i<=n-1;i++)
    cout<<' '<<q[i];
    puts("");
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)scanf("%d",&postorder[i]);
    for(int i=0;i<n;i++){
    scanf("%d",&inorder[i]);
    pos[inorder[i]]=i;
}
    build(0,n-1,0,n-1);
    bfs();
    return 0;
}