同題：UVa 00536 – Tree Recovery
小 Valentine 非常喜歡 2 元樹，她常常隨意的以大寫英文字母來建構 2 元樹。以下就是其中之一：
D
/ \
/ \
B E
/ \ \
/ \ \
A C G
/
/
F
為了把這 2 元樹保留起來，對每一 2 元樹她寫下 2 種字串。前序搜尋 preorder traversal（樹根，左子樹，右子樹）和中序搜尋（左子樹，樹根，右子樹）。所以上面那棵 2 元樹，她分別寫下了前序搜尋字串： DBACEGF 和中序搜尋字串： ABCDEFG。
現在你的任務就是要把小 Valentine 當年寫的這些字串還原成原來的 2 元樹，並且以後續搜尋 postorder traversal（左子樹，右子數，樹根）的方式列印出來。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| EOF 輸入，每筆測試資料一列。每列有 2 個字串，分別代表某一棵 2 元樹的前序及中序搜尋結果。2 個字串都只包含大寫英文字母，而且不會有重複的字母出現。所以最大長度都不會超過 26。 | 對每一列輸入，請輸出該 2 元樹以後序搜尋的結果。 |
| DBACEGF ABCDEFG BCAD CBAD | ACBFGED CDAB |
解題思路
前序的順序是：根、左、右
中序的順序是：左、根、右
使用遞迴的方式，將每次的根設置為前序字串的第一個字元，並且在中序字串中使用 For迴圈 尋找根，找到之後要再次呼叫函式，分別是左邊和右邊。
左邊：將前序的字串從位置 1 往右邊切 i 個字元，代表這就是左邊的資料。將中序從 0 往右切 i 個字元。如果根在第 0 個位置則不用呼叫左邊的函式了。
右邊：將前序的字串從位置 i+1 往右邊切 前序.length()-i-1 個字元。將中序從位置 i+1 往右邊切 前序.length()-i-1 個字元。如果根不在中序的最後一個位置，則不用呼叫。
每次函式呼叫完左右邊之後都要輸出這次的根。
範例程式碼－ZeroJudge C126: Tree Recovery
#include <iostream>
using namespace std;
void find(const string front, const string middle) {
const char root = front[0];
for (int i = 0; i<middle.length(); i++) {
if (middle[i] == root) {
if (i != 0) {
find(front.substr(1, i), middle.substr(0, i));
}
if (i != middle.length() - 1) {
find(front.substr(i+1, front.length()-i-1), middle.substr(i+1, front.length()-i-1));
}
cout << root;
}
}
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
string front, middle;
while (cin >> front >> middle) {
find (front, middle);
cout << "\n";
}
}
//ZeroJudge C126
//Dr. SeanXD