//提交通过，0.092，不算太快，先给出代码
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 10010 #define INF 100000010 struct treenode { int data,lchild,rchild,level; }; int *start,*flag; int min,leaf,pre,value; int input(int *post , int *ind) { int i,len; char ch; i=0; while(1) { if(scanf("%d",&ind[i++])==EOF) return 0; ch=getchar(); if(ch=='\n') break; } i=0; while(1) { if(scanf("%d",&post[i++])==EOF) return 0; ch=getchar(); if(ch=='\n') break; } return len=i; } int find(int len , int *s2 ,int key) { int i; for(i=0; i<len; i++) if(s2[i]==key) return i; return i; } void build_treenode_post_and_ind(int len , int *s1 , int *s2 , struct treenode *tree , int mark , int level) { int x,y,p; if(len<=0) { x=flag-start; if(mark==1) tree[x].lchild=-1; if(mark==2) tree[x].rchild=-1; return ; } x=flag-start; y=s1+len-1-start; tree[y].data=s1[len-1]; tree[y].level=level; level++; if(mark==1) tree[x].lchild=y; else if(mark==2) tree[x].rchild=y; p=find(len,s2,s1[len-1]); flag=s1+len-1; mark=1; build_treenode_post_and_ind(p,s1,s2,tree,mark,level); flag=s1+len-1; mark=2; build_treenode_post_and_ind(len-p-1,s1+p,s2+p+1,tree,mark,level); } void DFS(struct treenode *tree , int s , int sum) { int L,R; if(s<0) { if( (tree[pre].lchild==-1 && tree[pre].rchild==-1) && ( sum<min || (sum==min && tree[pre].data<value) ) ) { min=sum; leaf=pre; value=tree[pre].data; } return ; } else { sum+=tree[s].data; L=tree[s].lchild; R=tree[s].rchild; pre=s; DFS(tree,L,sum); pre=s; DFS(tree,R,sum); } } int main() { int i,len,level,mark,sum; int post[MAX],ind[MAX]; struct treenode tree[MAX]; while(1) { len=input(post , ind); if(!len) return 0; start=post; flag=NULL; mark=0; level=0; tree[0].lchild=tree[0].rchild=tree[0].level=-1; tree[0].data=0; build_treenode_post_and_ind(len,post ,ind ,tree,mark,level); min=INF; sum=0; leaf=pre=len-1; value=tree[len-1].data; i=len-1; //leaf保存最后的答案中叶子结点在树结点数组中的下标，valua是记录当最短路径长度一样 //叶子结点的最小值，pre是记录前驱的下标，i是根结点下标 DFS(tree,i,sum); //把整个树的结点数组，根结点的下标和当前的总和传过去 printf("%d\n",tree[leaf].data); } return 0; }