American Heritage
Farmer John takes the heritage of his cows very seriously. He is not, however, a truly fine bookkeeper. He keeps his cow genealogies as binary trees and, instead of writing them in graphic form, he records them in the more linear `tree in-order' and `tree pre-order' notations.
Your job is to create the `tree post-order' notation of a cow's heritage after being given the in-order and pre-order notations. Each cow name is encoded as a unique letter. (You may already know that you can frequently reconstruct a tree from any two of the ordered traversals.) Obviously, the trees will have no more than 26 nodes.
Here is a graphical representation of the tree used in the sample input and output:
C
/ \
/ \
B G
/ \ /
A D H
/ \
E F
The in-order traversal of this tree prints the left sub-tree, the root, and the right sub-tree.
The pre-order traversal of this tree prints the root, the left sub-tree, and the right sub-tree.
The post-order traversal of this tree print the left sub-tree, the right sub-tree, and the root.
PROGRAM NAME: heritage
INPUT FORMAT
Line 1:The in-order representation of a tree.Line 2:The pre-order representation of that same tree.
SAMPLE INPUT (file heritage.in)
ABEDFCHG
CBADEFGH
OUTPUT FORMAT
A single line with the post-order representation of the tree.
SAMPLE OUTPUT (file heritage.out)
AEFDBHGC
给出树的先序遍历，中序遍历
求后序遍历
递归处理，用[L1,R1],,[L2,R2]，分别表示递归处理到那颗子树
可以通过中序遍历得到树根，然后通过先序遍历分割开
Executing...
Test 1: TEST OK [0.000 secs, 4176 KB]
Test 2: TEST OK [0.000 secs, 4176 KB]
Test 3: TEST OK [0.000 secs, 4176 KB]
Test 4: TEST OK [0.000 secs, 4176 KB]
Test 5: TEST OK [0.000 secs, 4176 KB]
Test 6: TEST OK [0.000 secs, 4176 KB]
Test 7: TEST OK [0.000 secs, 4176 KB]
Test 8: TEST OK [0.000 secs, 4176 KB]
Test 9: TEST OK [0.000 secs, 4176 KB]
All tests OK.
Here are the test data inputs:
------- test 1 [length 18 bytes] ----
ABEDFCHG
CBADEFGH
------- test 2 [length 4 bytes] ----
F
F
------- test 3 [length 10 bytes] ----
BCAD
ABCD
------- test 4 [length 16 bytes] ----
GOLEAFS
SFAELOG
------- test 5 [length 20 bytes] ----
GSHBAQTPM
ABGHSPQTM
------- test 6 [length 32 bytes] ----
AUBYCVDZEWFXGTH
ZYUABVCDXWEFTGH
------- test 7 [length 40 bytes] ----
ABDCJHKILMNPOQFEGRS
ABCDEFHJIKLMNOPQGRS
------- test 8 [length 54 bytes] ----
GFDIHKLJMBNESRTPOQAUCWVZYX
ABDFGHIJKLMENOPRSTQCUVWXYZ
------- test 9 [length 54 bytes] ----
EHGDIFJLKMBNCOQSPRAWUXZYTV
ABDEGHFIJKLMCNOPQSRTUWXYZV
/*
ID:cqz15311
LANG:C++
PROG:heritage
*/
#include<cstdio>
#include<cstring>
char first[26];
char middle[26];
void dfs(int L1,int R1,int L2,int R2){
if (L1 > R1) return ;
if (L2 > R2) return ;
if (L1 == R1){
printf("%c",first[L1]);
return;
}
/*
处理
*/
char root = middle[L2];
int location;
for (int i=L1;i<=R1;i++){
if (root == first[i]){
location = i;
break;
}
}
dfs(L1,location-1,L2+1,L2+location-L1);
dfs(location+1,R1,L2+location-L1+1,R2);
printf("%c",middle[L2]);
}
int main(){
freopen("heritage.in","r",stdin);
freopen("heritage.out","w",stdout);
scanf("%s%s",&first,&middle);
int Len = strlen(first);
dfs(0,Len-1,0,Len-1);
puts("");
//又忘记了，这里一定要回车。
fclose(stdin);
fclose(stdout);
return 0;
}
/*
01234567
ABEDFCHG
CBADEFGH
*/
