题目：Tree
题意：给出树的中序和后序，找一个叶子是的它到根的路径上的权值和最小。
思路：用递归将树建立；再用dfs遍历树求权和！
参考：入门经典-例6-8-P156
代码：
#include <iostream> #include <string> #include <sstream> #include <algorithm> #include <stdio.h> using namespace std; const int maxv = 10010; int in_order[maxv],post_order[maxv],lch[maxv],rch[maxv]; int n; bool read_list(int *a){//读入数据 string line; if(!getline(cin,line)) return false; stringstream ss(line);//将字符串存入流中 n = 0; int x; while(ss >> x) a[n++] = x;//将数字分割出来 return n > 0; } int build(int L1,int R1,int L2,int R2){//递归建立树，L1,R1代表中序，L2,R2代表后序 if(L1 > R1) return 0;//当左大于右时停止 int root = post_order[R2];//后序的最后一个为根 int p = L1; while(in_order[p] != root) p++;//找到根位置 int cnt = p - L1;//因为中序的根在中间，所以减去L1后恰好算出左子树的个数 lch[root] = build(L1,p-1,L2,L2+cnt-1);//分别中序和后序的左子树 rch[root] = build(p+1,R1,L2+cnt,R2-1);//分别中序和后序的右子树 return root;} int best,best_sum; void dfs(int u,int sum){//先序：根，左，右 sum += u;//求权值和，注意不要写了递归式中！ if(!lch[u] && !rch[u]){//到达叶子 if(sum < best_sum || (sum == best_sum && u < best)){//筛选最小值 best = u; best_sum = sum; } } if(lch[u]) dfs(lch[u],sum);//左 if(rch[u]) dfs(rch[u],sum);//右 return;} int main() { while(read_list(in_order)) { read_list(post_order); build(0,n-1,0,n-1); best_sum = 999999999; dfs(post_order[n-1],0); printf("%d\n",best); } return 0; }