二叉树的遍历

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int pre[N],in[N],post[N];
int k;
struct node{
    int value;
    node *l,*r;
    node(int value=0,node *l=NULL,node *r=NULL):value(value),l(l),r(r){}    //初始化 
};
void buildtree(int l,int r,int&t,node* &root) {    //以先序为模板，先找根结点 
    int flag=-1;
    for(int i=l;i<=r;++i) if(in[i]==pre[t]) {    //再在中序中找左右子树 
        flag=i; break;
    }
    if(flag==-1) return;
    root = new node(in[flag]);
    ++t;
    if(flag>l)    buildtree(l,flag-1,t,root->l);    //求根结点的左子树 
    if(flag<r)    buildtree(flag+1,r,t,root->r);    //求根节点的右子树 
}
void preorder(node *root) {
    if(root) {
        post[++k]=root->value;
        preorder(root->l);
        preorder(root->r);
    }
}
void inorder(node *root) {
    if(root) {
        inorder(root->l);
        post[++k]=root->value;
        inorder(root->r);
    }
}
void postorder(node *root) {
    if(root) {
        postorder(root->l);
        postorder(root->r);
        post[++k]=root->value;
    }
}
void remove_tree(node *root) {    //释放空间 
    if(!root) return;
    remove_tree(root->l);
    remove_tree(root->r);
    delete root;
}
int main() {
    int n;
    while(~scanf("%d",&n)) {
        for(int i=1;i<=n;++i) scanf("%d",&pre[i]);
        for(int i=1;i<=n;++i) scanf("%d",&in[i]);
        node *root;
        int t=1;
        buildtree(1,n,t,root);
        k=0;
        postorder(root);
        for(int i=1;i<=n;++i)    printf("%d%c",post[i],i!=n?' ':'\n');
        remove_tree(root);
    }
    return 0;
}