欢迎访问我的Uva题解目录哦 https://blog.****.net/ri*qi/article/details/81149109

题目描述

题意解析

给一棵点带权（权值各不相同，都是小于10000的正整数）的二叉树的中序和后序遍历，找一个叶子使得它到根的路径上的权和最小。如果有多解，该叶子本身的权应尽量小。
输入中每两行表示一棵树，其中第一行为中序遍历，第二行为后序遍历。

算法设计

关于通过中根序列和后根序列重建一棵树的算法可以参考我的博客pat甲级1020. Tree Traversals (25)，在此不再赘述。本题与pat甲级1020. Tree Traversals (25)类似，只是需要处理一下输入数据，在重建树的过程中顺便求解符合要求的叶子结点即可。具体实现可见代码。

C++代码

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int data=0,left=-1,right=-1,pathValue=0;//数据域
};
Node inOrder[10005];
int postOrder[10005];
int ans=0,MINpath=INT_MAX;
int split(string&s,bool in){//分割字符串
    int size=0;
    string t="";
    for(int i=0;i<=s.size();++i)
        if(i==s.size()||s[i]==' '){
            if(in){
                inOrder[size].left=inOrder[size].right=-1;
                inOrder[size++].data=stoi(t);
            }else
                postOrder[size++]=stoi(t);
            t="";
        }else
            t+=s[i];
    return size;
}
int createTree(int left,int right,int root,int index){//根据中序序列、后序序列重建树
    if(left>right)
        return -1;
    int i=left;
    while(inOrder[i].data!=postOrder[root])//查找根在中根序列中的位置
        ++i;
    //更新从根结点到该结点的路径权值
    inOrder[i].pathValue=(index!=-1)?inOrder[index].pathValue+inOrder[i].data:inOrder[i].data;
    inOrder[i].left=createTree(left,i-1,root-1+i-right,i);//递归重建左子树
    inOrder[i].right=createTree(i+1,right,root-1,i);//递归重建右子树
    if(inOrder[i].left==-1&&inOrder[i].right==-1//是叶结点
        &&(inOrder[i].pathValue<MINpath//从根结点到该结点的路径权值小于当前最大路径权值
           ||(inOrder[i].pathValue==MINpath&&inOrder[i].data<inOrder[ans].data))){
            ans=i;//更新最小路径权值的叶子结点
            MINpath=inOrder[i].pathValue;//更新最小路径权值
        }
    return i;
}
int main(){
    string line;
    while(getline(cin,line)){
        int n=split(line,true);
        getline(cin,line);
        n=split(line,false);
        MINpath=INT_MAX;
        createTree(0,n-1,n-1,-1);
        printf("%d\n",inOrder[ans].data);
    }
    return 0;
}