输入格式:

第一行给出正整数N(≤)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。

输出格式:

在一行中输出Preorder:以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。

输入样例:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例:

Preorder: 4 1 3 2 6 5 7

这题唯一的难点就是如何根据后序和中序遍历把树建立起来

先模拟一下   比如后序是2 3 1 5 7 6 4   中序是1 2 3 4 5 6 7
从后序遍历可以知道4是树根，6是4的右孩子，然后根据中序遍历可知1 2 3是4的左子树，5 6 7 是右子树  所以1是4的左孩子，这样依次递归下去就可以把树建好了；
代码如下:
　　
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <set>
 4 #include <vector>
 5 #include <cstring>
 6 #include <algorithm>
 7 using namespace std;
 8 typedef long long ll;
 9 const int maxn=1e5+5;
10 int mid[50],post[50];
11 struct node
12 {
13     int data;
14     node *LNode;
15     node *RNode;
16 };
17 node* build(int *mid,int *post,int n)
18 {
19     if(n<=0)return NULL;
20     int *p=mid;
21     while(p)
22     {
23         if(*p==*(post+n-1))
24             break;
25         p++;
26     }
27     node *T=new node;
28     T->data=*p;
29     int len=p-mid;
30     T->LNode=build(mid,post,len);
31     T->RNode=build(p+1,post+len,n-len-1);
32     return T;
33 }
34 void preprint(node *T)
35 {
36     if(T)
37     {
38         printf(" %d",T->data);
39         preprint(T->LNode);
40         preprint(T->RNode);
41     }
42     return ;
43 }
44 int main()
45 {
46     int n;
47     cin>>n;
48     for(int i=0;i<n;i++)
49         scanf("%d",&post[i]);
50     for(int i=0;i<n;i++)
51         scanf("%d",&mid[i]);
52     node *T;
53     T=build(mid,post,n);
54     printf("Preorder:");
55     preprint(T);
56     printf("\n");
57     return 0;
58 }