题意 : 给你一颗二叉树，给定中序和后序，求叶子结点到根结点的最小值。
思路：由中序和后序求树，然后dfs~
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <sstream> #include <queue> using namespace std; #define maxn 10010 #define inf 0x3f3f3f3f int in[maxn]; int pos[maxn]; struct btnode { int v,l,r; btnode(){} btnode(int a,int b = -1,int c = -1) { v = a; l = b; r = c; } }tree[maxn]; int treenum = 0; int buildtree(int i,int inum, int p,int pnum) { if(inum <= 0) return -1; int rv = pos[p+pnum-1]; int root = treenum++; tree[root].v = rv; int j = i; while(in[j] != rv && j < i+inum-1) j++; int lnum = j-i, rnum = i+inum-j-1; tree[root].l = buildtree(i,lnum,p,lnum); tree[root].r = buildtree(j+1,rnum,p+lnum,rnum); return root; } int bfs() { queue<int> q; q.push(0); while(!q.empty()) { int temp = q.front(); q.pop(); cout<<tree[temp].v<<' '; if(tree[temp].l != -1) q.push(tree[temp].l); if(tree[temp].r != -1) q.push(tree[temp].r); } } int imin = inf,ans = -1; void dfs(int n,int sum) { if(tree[n].l == -1 && tree[n].r == -1) { if(sum < imin) imin = sum, ans = tree[n].v; else if(sum == imin) imin = sum, ans = min(tree[n].v,ans); return; } else { if(tree[n].l != -1) dfs(tree[n].l,sum+tree[tree[n].l].v); if(tree[n].r != -1) dfs(tree[n].r,sum+tree[tree[n].r].v); } } int main() { string mid; while(getline(cin,mid)) { treenum = 0; stringstream ss; ss << mid; int midnum = 0; int temp; while(ss >> temp) in[midnum++] = temp; for(int i = 0; i < maxn; i++) tree[i] = btnode(0); for(int i = 0; i < midnum; i++) scanf("%d",&pos[i]); getchar(); ans = -1,imin = inf; buildtree(0,midnum,0,midnum); dfs(0,tree[0].v); printf("%d\n",ans); } return 0; }