【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d432
【姊妹題】d861: NOIP2001 3.求先序排列
【解題想法】Divide & Conquer
- 使用字元的 ASCII code 當 post_idx 陣列的 index，post_idx 紀錄「後序字串」各個字元出現的順序。
- 從「中序字串」中找出在「post_idx 陣列」中值最大的（就是在後序字串中位置最後面的）字元，該字元即為目前 subtree 的 root（下例中的「A」）。
- 輸出 root 字元，再利用它把「中序字串」分成 left tree 和 right tree。
- 重複標準 Divide & Conquer 做法。
#include <iostream>
using namespace std;
// ASCII code
// 0: 48 (decimal), A: 65, a: 97
int post_idx[100], n;
string in, post;
void func(int in_start, int in_end){
// 在中序字串中找出root，其在「後序字串中的index值」最大
if (in_start != in_end){
int mx = -1, root;
for (int i = in_start; i < in_end; i++){
if (post_idx[in[i]-'0'] > mx){
mx = post_idx[in[i]-'0'];
root = i;
}
}
cout << in[root];
// left tree
func(in_start, root);
// right tree
func(root+1, in_end);
}
}
int main() {
while(cin >> in >> post){
n = in.length();
for (int i = 0; i < n; i++){
// 用「後序字串」字元的ASCII code當post_idx的index
post_idx[post[i] - '0'] = i;
}
func(0, n);
cout << "\n";
}
}