NYOJ-221 Tree(前の順序で後順を押す)
3161 ワード
Tree
時間制限:
1000 ms | メモリ制限:
65535 KB
難易度:
3
説明
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:
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!
入力
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.
出力
For each test case、recover Valentine's binary tree and print one line containing the tree's postorder trversal(left subtree、right subtree、root)
サンプル入力
苗床棟
考え方:
前の順序と中の順序が分かりました.後の順序を押します.
総体的な考え方はそれぞれの構造(順序)の特徴を通して三つのものを探し出すことです.
前列が巡回している構造は「ルート左右」であり、中順序は「左根右」であり、後の順序は「左右のルート」であり、現在のノードの左右のツリーにおいても同様の構造であることが分かる.
したがって、既知のプリアンブルおよび中間順序の場合は、順に基づいてルートの値を決定し、中間順序に従って左右のサブツリーの長さを決定し、その後、再帰すればよい.
コード:
時間制限:
1000 ms | メモリ制限:
65535 KB
難易度:
3
説明
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!
入力
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.
出力
For each test case、recover Valentine's binary tree and print one line containing the tree's postorder trversal(left subtree、right subtree、root)
サンプル入力
DBACEGF ABCDEFG
BCAD CBAD
サンプル出力ACBFGED
CDAB
アップロード者苗床棟
考え方:
前の順序と中の順序が分かりました.後の順序を押します.
総体的な考え方はそれぞれの構造(順序)の特徴を通して三つのものを探し出すことです.
前列が巡回している構造は「ルート左右」であり、中順序は「左根右」であり、後の順序は「左右のルート」であり、現在のノードの左右のツリーにおいても同様の構造であることが分かる.
したがって、既知のプリアンブルおよび中間順序の場合は、順に基づいてルートの値を決定し、中間順序に従って左右のサブツリーの長さを決定し、その後、再帰すればよい.
コード:
#include
#include
char a[30], b[30];
void f(int l_s, int l_e, int r_s, int r_e);
int main()
{
while(~scanf("%s%s", a, b)){
int len = strlen(a) - 1;
f(0, len, 0, len);
printf("
");
}
return 0;
}
void f(int l_s, int l_e, int r_s, int r_e)
{
if(l_e < l_s) return;
if(l_e == l_s){
printf("%c", b[r_s]);
return;
}
int i;
for(i = r_s; ; i++){
if(b[i] == a[l_s]) break;
}
int len = i - r_s;
f(l_s + 1, l_s + len, r_s, i - 1);
f(l_s + len + 1, l_e, i + 1, r_e);
printf("%c", b[i]);
}