「資訊社」發展了一個獨特的進入社團時所用的通關密語，為了保密起見每天都
會有不同的通關密語。通關密語是由一串不同的大小寫英文字母及０到９的數字
字元所組成，且其長度最多為６０個字元，大小寫英文字元視為不同。社長每天
將該天的密語放置於可以由前序巡行 (pre-order traversal) 產生該密語的二元樹
內。且將中序巡行 (in-order traversal) 及後序巡行 (post-order traversal) 所得的字
串傳送給所有的社員。請你寫一個程式，給定某一天所收到的中序巡行及後序巡
行字串，請解出該天的通關密語。二元樹巡行方式範例如下所示：
給定一個二元樹，中序巡行方式為在任一頂點時 (root) 先輸出左邊子樹所有字
元，再輸出該頂點的字元，最後輸出右邊子樹所有字元。每一個子樹字元輸出方
式也如上所述。前序巡行方式則在任一頂點時 (root) 先輸出頂點的字元，再輸
出左邊子樹所有字元，最後輸出右邊子樹所有字元。而後序巡行方式則在任一頂
點時 (root) 先輸出左邊子樹所有字元，再輸出右邊子樹所有字元，最後輸出頂
點的字元。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 其內容有兩行字串。第一行字串是中序巡行所得的字 串，第一行字串則是後序巡行所得的字串。 | 請輸出一行的通關密語至輸出檔 |
| 1xB2Ay3C4z x12By3z4CA | AB1x2C3y4z |
解題思路
使用中序和後序來求前序。可以使用遞回來切字串，每次進入遞迴的時候都輸入目前中序的第一個字元，也就是根。然後再呼叫左右兩邊的函式，可以參考 C126 的解題思路。
範例程式碼－ZeroJudge D432: 通關密語 (pwd)
#include <iostream>
using namespace std;
void find(const string middle, const string back) {
const char root = back[back.length()-1];
cout << root;
for (int i = 0; i<middle.length(); i++) {
if (middle[i] == root) {
if (i != 0) {
find(middle.substr(0, i), back.substr(0, i));
}
if (i != middle.length()-1) {
find(middle.substr(i+1, middle.length()-i-1), back.substr(i, back.length()-i-1));
}
}
}
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
string middle, back;
while (cin >> middle >> back) {
find (middle, back);
cout << "\n";
}
}
//ZeroJudge D432
//Dr. SeanXD