本文共 1135 字，大约阅读时间需要 3 分钟。

题意：

给定中序遍历和后序遍历，然后建树，最后找出一个叶子到根的路径权值最小（权和相同时，选择叶子权值小的那个）。

代码：

#include<iostream>#include<algorithm>#include<cstring>#include<sstream>#include<cstdio>#include<queue>#include<cmath>#include<set> #include<map>using namespace std; const int maxn=1e4+50;int in[maxn],post[maxn],lch[maxn],rch[maxn]; //中序，后序，左子树，右子树int x,c,ans,sumans;string s;int build(int zz,int zy,int hz,int hy)  //静态建树          // 中左(中序遍历第一个)  中右(中序遍历最后一个)  后左  后右 {   	if(hz>hy) return 0;	int root=post[hy];	int p=zz;	for(;p<=zy;p++) if(root==in[p]) break;	int num=p-zz;	lch[root]=build(zz,p-1,hz,hz+num-1);	rch[root]=build(p+1,zy,hz+num,hy-1);	return root;}void dfs(int u,int sum) //从根出发找到叶子{   	sum+=u;	if(!lch[u] && !rch[u]) //叶子	{   		if(sumans>sum || (sumans==sum && u<ans)) 		{   			ans=u;			sumans=sum;		}	}	if(lch[u]) dfs(lch[u],sum);	if(rch[u]) dfs(rch[u],sum);}int main(){   		while(getline(cin,s))	{   		stringstream ss(s);		c=0;		while(ss>>x) in[c++]=x;	    	    c=0;	    getline(cin,s);	    stringstream sss(s);	    while(sss>>x) post[c++]=x;	    	    build(0,c-1,0,c-1); 	    sumans=1<<27; //初始，很大的值	    dfs(post[c-1],0);	    cout<<ans<<endl;	}	return 0;}