欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVA 548 - Tree(树)

程序员文章站 2022-04-14 20:42:16
...

例题6-8 树(Tree, UVa 548)
给一棵点带权(权值各不相同,都是小于10000的正整数)的二叉树的中序和后序遍
历,找一个叶子使得它到根的路径上的权和最小。如果有多解,该叶子本身的权应尽量小。
输入中每两行表示一棵树,其中第一行为中序遍历,第二行为后序遍历。
样例输入:
3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255
样例输出:
1
3
255

本家地址


在根据中序和后序遍历进行构造的时候,同时计算叶子的权值和,比较选择最小的权值的叶子,记录最小权值和的叶子和权值和。

#include<iostream>
#include<cstdio>
#include<sstream>
#include<cstring>
using namespace std;

int inorder[10004];
int postorder[10004];
int inindex[10004];

int min_top_value = 100000004; // 最小的权和
int loft = -1;  // 叶子本身的值,
/* 参数: 当前子树的 中序前,后 后序前,后 */
int calcul(int in_begin, int in_end, int post_begin, int post_end, int alculate_root_value){
    // in_end - in_begin == post_end - post_begin
    int root_value = postorder[post_end]; // 根, 从后序
    int root_in_index = inindex[root_value];//fin_inorder(in_begin, in_end, root_value);

    alculate_root_value = alculate_root_value + root_value; // 新的累计根值, 加上自己身上的

    if(in_end <= in_begin){ // 叶子了
        if(loft == -1 ||  // 第一个叶子
            (alculate_root_value < min_top_value) ||  
            (alculate_root_value == min_top_value && inorder[in_begin] < loft) ) {
                min_top_value = alculate_root_value;
                loft = inorder[in_begin];
            }
        return 0;
    }

    int len = root_in_index-1-in_begin;

    if(root_in_index > in_begin){
        calcul(in_begin, root_in_index-1,
                post_begin, post_begin + len, 
                alculate_root_value); // 左枝
    }

    len = in_end - root_in_index-1;
    if(root_in_index < in_end){
        calcul(root_in_index+1, in_end, 
                post_end-1-len , post_end-1, 
                alculate_root_value); // 右枝
    }

    return 0;
}

void init(){
    memset(inorder,0,sizeof(inorder));
    memset(postorder,0,sizeof(postorder));
    memset(inindex,0,sizeof(inindex));
    min_top_value = 100000004; // 最小的权和
    loft = -1;  // 叶子本身的值
}

int main()
{
    int row = 0;
    string line;
    while(getline(cin,line)){
        // cout<<n<<" ";
        stringstream ss(line);
        int i=0;
        int n;
        
        if(row==0){
            // 新的一组, 要初始化
            // 代表是一组中的第一行,即中序遍历
            init();
            while(ss>>n){
                inorder[i] = n;
                inindex[n] = i;
                i++;
            }
            row = 1;
        }else{
            // 一组中的第二行, 即后序遍历
            while(ss>>n){
                postorder[i++] = n;
            }
            row = 0;
            calcul(0,i-1,0,i-1,0);
            cout<<loft<<endl;
        }
    return 0; 
}
// AC at 2020/03/21

ps:债还清了,这个代码提交了12次数,uva因为赞助商跑路的关系(不知道也没有关系),感觉现在更加慢了。网站首页筹集代码贡献。也想做点贡献,但是C++的网站。。。

相关标签: uva.onlinejudge.org