[patl2-011]玩转二叉树

解题关键：数据结构课本上的裸题。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct mm{int l,r;}tr[1000];
int arr[1000];
int brr[100];
queue<int>que;
int build(int la,int ra,int lb,int rb){
    if(la>ra) return 0;
    int root=brr[lb];
    int p=la;
    while(arr[p]!=root) p++;
    int cnt=p-la;
    tr[root].l=build(la,p-1,lb+1,lb+cnt);
    tr[root].r=build(p+1,ra,lb+cnt+1,rb);
    return root;
}
void revers(int root){
    if(root){
        swap(tr[root].l,tr[root].r);
        revers(tr[root].l);
        revers(tr[root].r);
   }
}
int flag;
void bfs(){
    int root=brr[0];
    que.push(root);
    while(!que.empty()){
        int t=que.front();
        que.pop();
        if(flag==1){
            printf(" %d",t);}
        else{
            printf("%d",t);flag=1;
        }
        if(tr[t].l) que.push(tr[t].l);
        if(tr[t].r) que.push(tr[t].r);
    }
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",arr+i);
    }
    for(int i=0;i<n;i++){
        scanf("%d",brr+i);
    }
    build(0,n-1,0,n-1);
    revers(brr[0]);
    bfs();
}