USACO American Heritage

这题在很多书籍上都出现过，可以说是基础了，不知为何USACO把它放在这里，由于数据规模很小，使用递归解决很方便。

代码如下：

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #define MAXLENGTH 30
05
06 int n;
07 char in_order[MAXLENGTH],pre_order[MAXLENGTH];
08 int in_location[255];
09
10 //一边计算一边输出结果，省去额外构建树的空间
11 void create_tree(int ib,int pb,int len)
12 {
13     if(len == 1)
14     {
15         printf("%c",pre_order[pb]);
16         return;
17     }
18     if(in_location[pre_order[pb]] > ib)    //have left sub-tree
19     {
20         create_tree(ib,pb + 1,in_location[pre_order[pb]] - ib);
21     }
22     if(in_location[pre_order[pb]] < ib + len - 1)    //have right sub-tree
23     {
24         create_tree(in_location[pre_order[pb]] + 1,pb + in_location[pre_order[pb]] - ib + 1,len - (in_location[pre_order[pb]] - ib) - 1);
25     }
26     printf("%c",pre_order[pb]);
27 }
28
29 void locate(int *arr,char *str)     //预处理字符的位置
30 {
31     int i;
32     for(i = 0;i < n;i ++)
33         arr[(int)str[i]] = i;
34 }
35
36 int main()
37 {
38     freopen("heritage.in","r",stdin);
39     freopen("heritage.out","w",stdout);
40     scanf("%s\n",in_order);
41     scanf("%s",pre_order);
42     n = strlen(in_order);
43     locate(in_location,in_order);
44     create_tree(0,0,n);
45     putchar('\n');
46     return 0;
47 }