UVa536

題目:
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=477

#include <bits/stdc++.h>
using namespace std;

void solve(string pre, string in){
    if(pre.empty() || in.empty()) return; // 檢查 如果是空樹就返回 代表不能再切了
    char root = pre[0]; // pre order的第一個值就是root
    int in_root_idx = in.find(root); // 去找in order的root，就可以得到左右子樹的分割點
    
    string in_left = in.substr(0, in_root_idx); // 將in order切成左右子樹與root三塊
    string in_right = in.substr(in_root_idx+1);

    string pre_left = pre.substr(1, in_root_idx); // 將pre order切成左右子樹與root三塊
    string pre_right = pre.substr(in_root_idx+1);

    // post order -> 左 右 中
    solve(pre_left, in_left); // 把左邊繼續切
    solve(pre_right, in_right); // 把右邊繼續切
    printf("%c", root); // 切到沒東西了會自動return回來 然後輸出
}

int main(){
    string pre, in;
    while(cin >> pre >> in){
        solve(pre, in);
        printf("\n");
    }
    return 0;
}