这道题的关键字在于根据中序遍历和后序遍历建立出二叉树。另外在寻找路径时，可使用深度优先的方式搜索，搜索到叶子节点时加以判断即可。 这里用到sstream来读入，也是一个技巧，记录下来。 代码如下：
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<string> #include<sstream> using namespace std; const int maxn = 10005; const int root = 1; int Left[maxn], Right[maxn]; int Value[maxn]; int ins[maxn], pos[maxn]; int n; int cnt; int bestSum = 1000000000; int best; bool getinput(int a[]){ string s; if (!getline(cin,s)) return false; stringstream ss(s); n = 0; int x; while (ss >> x){ a[n++] = x; } return true; } void newTree(){ cnt = 0; Left[root] = Right[root] = 0; Value[root] = -1; } int newNode(){ ++cnt; Left[cnt] = Right[cnt] = 0; Value[cnt] = -1; return cnt; } int build(int L1, int R1, int L2, int R2){ int t = 0; if (L1 <= R1){ int v = pos[R2]; t = newNode(); Value[t] = v; int i; for (i = L1; i <= R1; i++){ if (ins[i] == v) break; } int cnt = i - L1; Left[t] = build(L1, i - 1, L2, L2+cnt-1); Right[t] = build(i + 1, R1, L2 + cnt, R2-1); } return t; } void dfs(int p,int sum){ sum += Value[p]; if (!(Left[p] || Right[p])){ if (sum < bestSum || (sum == bestSum && Value[p] < best)){ best = Value[p]; bestSum = sum; } } else{ if (Left[p]) dfs(Left[p], sum); if (Right[p]) dfs(Right[p], sum); } } int main() { while (getinput(ins)){ getinput(pos); newTree(); build(0, n-1, 0, n-1); bestSum = 1000000000; best = 10000; dfs(root,0); cout << best << endl; } return 0; }