Poj 2255 Tree Recovery

1.Link:
http://poj.org/problem?id=2255
2.コンテント：
Tree Recovery
Time Limit：1000 MS
 
メモリLimit：65536 K
Total Submissions:11448
 
Acceepted:7186
Description
Little Valentine liked playing with binary trees very much.Her favorite game was constructing rand mly looking binary trees with capital letters in the nodes.
This is an example of one of her creations:

                                               D


                                              / \


                                             /   \


                                            B     E


                                           / \     \


                                          /   \     \


                                         A     C     G


                                                    /


                                                   /


                                                  F

Torecorder trees for future generation s、she wrote down twostins for each tree:a preorder trversal(root、left subtree、rightsubtree)and n inorder trtrtrsal(left subtree、roote、rototrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtre))FFFFFFFtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtreeeeeedededededededededededer
She thought that such a pair of stregs would give enough information to reconstruct the tree later(but she never tried it)
Now、years later、looking again the streings、she realized that reconstructining the trees indeed possible、but only because she never had the same letter twice in the same tree.
However，dong the reconstruction by hand，son turned out to be tedious.
So now she asks you to write a program that does the job for her！
Input
The input will contain one or more test cases.
Each test case consists of one line containing two streings preord and inord，representing the preorder trversal and inorder trversal of a binary tree.Both stings consist of unique capital letters.
Input is terminated by end of file.
Output
For each test case、recover Valentine's binary tree and print one line containing the tree's postorder trversal(left subtree、right subtree、root)
Sample Input

DBACEGF ABCDEFG

BCAD CBAD

Sample Output

ACBFGED

CDAB

ソurce
Ulm Local 1997
3.Method:
4.コード:

 1 #include "stdio.h"

 2 #include "string.h"

 3 #define NUM 27

 4 char ans[NUM];

 5 int pos;

 6 void func(char a[],char b[],int al,int bl,int len)

 7 {

 8     int i;

 9     if(len==0) return;

10     else if(len==1) ans[pos--]=a[al];

11     else

12     {

13         ans[pos--]=a[al];

14         for(i=bl;i<bl+len;i++) if(b[i]==a[al]) break;

15         func(a,b,al+(i-bl)+1,i+1,bl+(len-1)-i);

16         func(a,b,al+1,bl,i-bl);    

17     }

18 }

19 int main()

20 {

21     char a[NUM],b[NUM];

22     int len;

23     while(scanf("%s%s",a,b) != EOF)

24     {

25         len=strlen(a);

26         pos=len-1;

27         func(a,b,0,0,len);

28         ans[len]='\0';

29         printf("%s
",ans);

30     }

31     return 0;

32 }

 
5.レフェレン