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++的网站。。。
推荐阅读
-
element-tree-grid(表格树)的使用
-
珂朵莉树(Chtholly Tree)学习笔记
-
JS--插件: 树Tree 开发与实现
-
浅谈线段树 Segment Tree
-
jquery使用EasyUI Tree异步加载JSON数据(生成树)
-
BZOJ2212: [Poi2011]Tree Rotations(线段树合并)
-
HDU 4786Fibonacci Tree(最小生成树)
-
洛谷P4180 [Beijing2010组队]次小生成树Tree
-
【leetcode】-700. Search in a Binary Search Tree 查找二叉搜索树
-
EasyUI Tree树组件无限循环的解决方法