2. 中序和后序重建二叉树转前序遍历（POJ 由中根序列和后根序列重建二叉树）

题目链接：http://dsalgo.openjudge.cn/huawen05/1/
AC代码：

#include<bits/stdc++.h>
using namespace std;
#define eps 1e-8
#define INF 0x3f3f3f3f
const int num=1e6;

int a[num+5],b[num+5],n[num+5],ans[num+5],cnt;
struct node{
    int x;
    node* left;
    node* right;
    node(int _x=0){
        x=_x;
        left=NULL;
        right=NULL;
    }
};

node* buildtree(int l1,int r1,int l2,int r2)
{
    //cout<<l1<<' '<<r1<<' '<<l2<<' '<<r2<<"###"<<endl;
    if(l1>r1)  return NULL;
    if(l1==r1){
        node* nd=new node(a[l1]);
        return nd;
    }
    node* nd=new node(b[r2]);
    int tmp=b[r2],id=l1;
    for(int i=l1;i<=r1;i++){
        if(a[i]==tmp){
            id=i;
            break;
        }
    }
    nd->left=buildtree(l1,id-1,l2,l2+id-l1-1);
    nd->right=buildtree(id+1,r1,l2+id-l1,r2-1);
    return nd;
}

void pre_order(node* nd){
    if(nd==NULL)    return;
    ans[cnt++]=nd->x;
    pre_order(nd->left);
    pre_order(nd->right);
}

int main()
{
    int k=0;
    cnt=0;
    while(~scanf("%d",&n[k++])){}
    for(int i=0;i<k/2;i++){
        a[i]=n[i];
        b[i]=n[i+k/2];
    }
    node* tree=buildtree(0,k/2-1,0,k/2-1);
    pre_order(tree);
    for(int i=0;i<cnt-1;i++){
        printf("%d ",ans[i]);
    }
    printf("%d\n",ans[cnt-1]);
    return 0;
}