c126. 00536 - Tree Recovery
Tags : tree
Accepted rate : 488人/514人 ( 95% ) [非即時]
評分方式:
Strictly

最近更新 : 2015-08-28 15:08

Content

小Valentine非常喜歡2元樹,她常常隨意的以大寫英文字母來建構2元樹。以下就是其中之一:

D
/ \
/ \
B E
/ \ \
/ \ \
A C G
/
/
F

為了把這2元樹保留起來,對每一2元樹她寫下2種字串。前序搜尋 preorder traversal(樹根,左子樹,右子樹)和中序搜尋(左子樹,樹根,右子樹)。所以上面那棵2元樹,她分別寫下了前序搜尋字串: DBACEGF 和中序搜尋字串: ABCDEFG

現在你的任務就是要把小Valentine當年寫的這些字串還原成原來的2元樹,並且以後續搜尋 postorder traversal(左子樹,右子數,樹根)的方式列印出來。

Input

每筆測試資料一列。每列有2個字串,分別代表某一棵2元樹的前序及中序搜尋結果。2個字串都只包含大寫英文字母,而且不會有重複的字母出現。所以最大長度都不會超過26。

Output

對每一列輸入,請輸出該2元樹以後序搜尋的結果。

Sample Input #1
DBACEGF ABCDEFG
BCAD CBAD
Sample Output #1
ACBFGED
CDAB
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1K
Hint :

* Luck 貓翻譯

Tags:
tree
出處:
UVa536

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」