c126-acm-536-TreeRecovery

內容：

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

D

/ \

B E

/ \ \

A C G

/

F

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

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

輸入說明：

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

輸出說明：

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

範例輸入：

DBACEGF ABCDEFG BCAD CBAD

範例輸出：

ACBFGED CDAB

提示：

背景知識： TREE

* Luck 貓翻譯

出處：

ACM 536

解題策略

利用preorder順序的第一個字元為樹的root特性，利用此字元將inorder左半與右半，再不斷遞迴下去建立原本的樹，再寫postorder走訪程式。