已知二叉樹的中序遍歷和后序遍歷，構建二叉樹，求葉子到根的最小路徑權值和；

后序遍歷的最后一個字符即為二叉樹的根結點，然后在中序遍歷中找到這個根結點的位置，根結點的左邊序列即為該根的左子樹，右邊序列即為右子樹，然后再在后序遍歷中找左右子樹的根結點，以此類推，用遞歸遍歷。

#include<bits/stdc++.h>#define INF 0x3f3f3f3fusing namespace std;const int maxn = 1e4+5;int in_order[maxn], post_order[maxn];int lch[maxn], rch[maxn];int cnt;bool read_input(int* a){    cnt = 0;    string s;    if(!getline(cin, s))    return false;    int len = (int)s.size();    int tmp = 0;    for(int i = 0;i<len;i++){        if(s[i] == ' '){            a[cnt++] = tmp;            tmp = 0;            continue;        }        tmp = tmp*10+(s[i]-'0');    }    a[cnt++] = tmp;    if(cnt > 0) return true;    else    return false;}int build(int L1, int R1, int L2, int R2){    if(L1 > R1) return 0;       //空樹    int root = post_order[R2];    int i;    for(i = L1;i<=R1;i++){        if(in_order[i] == root)            break;    }    int k = i-L1;    lch[root] = build(L1, i-1, L2, L2+k-1);    rch[root] = build(i+1, R1, L2+k, R2-1);    return root;}int ans, tmp;void dfs(int u, int sum){    if(u == 0)  return;    sum += u;    if(!lch[u] && !rch[u]){     //葉子        if(ans > sum || (ans == sum && tmp > u)){            ans = sum;            tmp = u;        }        return;    }    dfs(lch[u], sum);    dfs(rch[u], sum);}int main(){    while(read_input(in_order)){        read_input(post_order);        build(0, cnt-1, 0, cnt-1);        ans = INF;        dfs(post_order[cnt-1], 0);        cout<<tmp<<endl;    }    return 0;}