UVA 548 根据中序和后序建立二叉树并求根到叶的最短路

 题意：根据中序和后序建立二叉树并求根到叶的最短路

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<sstream>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int MAXN=10010;
int l[MAXN];
int r[MAXN];
int inorder[MAXN];
int postorder[MAXN];
int minx,pos;
int build(int L1,int R1,int L2,int R2)//中序[L1,R1]和后序[L2,R2]建立一棵二叉树，返回根节点序号
{
    if(L1>R1||L2>R2)
        return 0;
    int root=postorder[R2];
    int p=L1;
    while(inorder[p]!=root)
        p++;
    int cnt=p-L1；;
    l[root]=build(L1,p-1,L2,L2+cnt-1);
    r[root]=build(p+1,R1,L2+cnt,R2-1);
    return root;
}
void dfs(int t,int sum)
{
    sum+=t;
    if(l[t]==0&&r[t]==0)//搜到叶节点就判断
    {
        if(sum<minx)
        {
            minx=sum;
            pos=t;
        }
        return ;
    }
    if(l[t]>0)
        dfs(l[t],sum);
    if(r[t]>0)
        dfs(r[t],sum);
}
int main()
{
    string str;
    while(getline(cin,str))
    {
        stringstream ss;
        ss<<str;
        int a;
        int k=0;
        while(ss>>a)
        {
            inorder[k++]=a;
        }
        getline(cin,str);
        stringstream sx;
        sx<<str;
        k=0;
        while(sx>>a)
        {
            postorder[k++]=a;
        }
        int root=build(0,k-1,0,k-1);
        minx=inf;
        dfs(root,0);
        cout<<pos<<endl;
    }
    return 0;
}