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

题意：给你一棵树的中序和后序遍历，让你求一个叶节点使得叶节点到根节点的权值最小，若有多解则输出权值最小的叶子。

思路：根据树的中序和后序遍历来建树，在建树的时候可以用数组来表示数，把结点的左右子树放进两个数组里面，在求解答案的时候在递归求解。

#include 
   
    #include 
    
     using namespace std;const int maxn=1e4+50;int in_order[maxn];int past_order[maxn];int lch[maxn];int rch[maxn];int n;bool read_line(int *a){    string s;    getline(cin,s);    int x;    int cnt=0;    stringstream ss ;    ss.clear();    ss << s;    while(ss>>x)    {        a[cnt++]=x;    }    n=cnt;    return cnt>0;}int Build(int l1,int r1,int l2,int r2)//zhong  hou{    if(l1>r1) return 0;    int root=past_order[r2];    int p=l1;    while(in_order[p]!=root) p++;    int cnt=p-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;int sum;void dfs(int x,int cnt){    cnt+=x;    if(lch[x]==0&&rch[x]==0)    {        if(cnt
     
    
   

转载地址：http://afgsi.baihongyu.com/