UVA-548
题目：给一棵点带权（权值各不相同，都是小于10000的正整数）的二叉树的中序和后序遍历，找一个叶子使得它到根的路径上的权和最小。如果有多解，该叶子本身的权应尽量小。输入中每两行表示一棵树，其中第一行为中序遍历，第二行为后序遍历。(题目翻译取自刘汝佳《算法竞赛入门经典》P155)。
#include<cstdio> #include<cmath> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<vector> #include<sstream> using namespace std; const int MAXN = 20000; int inOrder[MAXN],postOrder[MAXN],l_tree[MAXN],r_tree[MAXN]; int best,best_leave,n; bool input(int *a){ string s; while(!getline(cin,s)) return false; stringstream ss(s); int x; n = 0; while(ss>>x) a[n++] = x; return n>0; } int build(int L1,int R1,int L2,int R2){ if(L1>R1) return 0; //为空树 int root = postOrder[R2]; int p = L1; while(inOrder[p]!=root) p++; int count = p - L1; //根坐标为root的左子树的节点个数 l_tree[root] = build(L1, p-1, L2, L2+count-1); //l_tree[root]指 根坐标为root的左子树的根坐标的值 r_tree[root] = build(p+1, R1, L2+count, R2-1); //r_tree[root]指 根坐标为root的右子树的根坐标的值 return root; } void dfs(int u,int sum){ sum += u; if(!l_tree[u]&&!r_tree[u]){ //根坐标为u的节点没有左子树也没有右子树，则u是一片叶子 if(sum<best||(sum==best&&u<best_leave)){ best = sum; //到目前为止的最优解的对应权值和 best_leave = u; } } if(l_tree[u]) dfs(l_tree[u],sum); if(r_tree[u]) dfs(r_tree[u],sum); } int main() { while(input(inOrder)){ input(postOrder); build(0,n-1,0,n-1); best = 1<<30; //best取很大数 dfs(postOrder[n-1],0); cout<<best_leave<<endl; } return 0; }思路：后序遍历的最后一个字符是根，因此只需在中序遍历中找到它，就知道左右子树的中序和后序遍历了。从而可以据此构造二叉树。最后递归遍历，求出最优解。
