【日常学习】【二叉树遍历】Uva548 - Tree题解

妖狐艹你老母 2022-08-07 05:56 176阅读 0赞

这道题目本身不难，给出后序遍历和中序遍历，求到节点最小路径的叶子，相同长度就输出权值小的叶子。

Uva上不去了，没法测。基本上是按照ruka的代码来的。直接上代码

//Uva548 Tree
    #include<iostream>
    #include<algorithm>
    #include<string>
    #include<sstream>
    #include<cctype>
    using namespace std;
    
    const int maxv=10000+10;
    int inorder[maxv],postorder[maxv],l[maxv],r[maxv];
    int n;
    int best,best_num;
    
    bool read_list(int *a){
    	string line;
    	if (!getline(cin,line)) return false;
    	stringstream ss(line);
    	n=0;
    	int x;
    	while (ss>>x) a[n++]=x;
    	return n>0;
    }
    
    int build(int l1,int r1,int l2,int r2){
    	if (l1>r1) return 0;//notice
    	int root=postorder[r2];
    	int p=0;
    	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 now,int sum){
    	sum+=now;
    	if ((!l[now])&&(!r[now])){
    		if ((sum<best_num)||((sum==best_num)&&(now<best))){
    			best=now;
    			best_num=sum;
    		}
    	}
    	if (l[now]) dfs(l[now],sum);
    	if (r[now]) dfs(r[now],sum);
    } 
    
    int main(){
    	freopen("1.txt","r",stdin);
    	freopen("2.txt","w",stdout);
    	while (read_list(inorder)){//every time you read an inorder
    		read_list(postorder);
    		build(0,n-1,0,n-1);//build a tree
    		best_num=1000000000;
    		dfs(postorder[n-1],0);
    		cout<<best<<endl;;
    	}
    	return 0;
    }

五一又要出去培训了，要求相当高，我要抓紧时间学习了。

——长风破浪会有时，直挂云帆济沧海

发表评论取消回复

表情：

评论列表（有 0 条评论，176人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉树二叉树遍历通过二叉树遍历求得二叉树

什么是二叉树 > > 二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且

偏执的太偏执、/ 2022年12月04日 01:08/ 0 赞/ 285 阅读

相关【日常学习】【二叉树遍历】Uva548 - Tree题解

这道题目本身不难，给出后序遍历和中序遍历，求到节点最小路径的叶子，相同长度就输出权值小的叶子。 Uva上不去了，没法测。基本上是按照ruka的代码来的。直接上代码

妖狐艹你老母/ 2022年08月07日 05:56/ 0 赞/ 177 阅读

相关 POJ2255 Tree Recovery(二叉树遍历)

题目大意：给出先序遍历和中序遍历的结果，求后序遍历。采用递归算法：依次选取先序字符串，以选取字符为界限分割中序字符串为左子树和右子树，分别递归，直至不可分割。

不念不忘少年蓝@/ 2022年07月11日 07:41/ 0 赞/ 178 阅读

相关遍历二叉树

遍历二叉树今天我们学习了二叉树，现在我就基于二叉树的递归定义来说一说遍历二叉树的三种方法：先序、中序和后序。根据二叉树的递归定义可知，二叉树是由3个基本单元组成：根结点

傷城~/ 2022年06月05日 08:11/ 0 赞/ 332 阅读

相关 uva122 二叉树的层次遍历

Trees are fundamental in many branches of computer science (Pun definitely intended)

ゞ浴缸里的玫瑰/ 2022年05月31日 01:48/ 0 赞/ 164 阅读

相关二叉树遍历

前序遍历（左中右）ABDGHCEIF ![前序遍历][70] 中序遍历（左根右）GDHBAEICF![中序遍历][70 1] 后序遍历（左右根）GHDBIEFCA![

Bertha 。/ 2022年05月11日 13:48/ 0 赞/ 341 阅读

相关二叉树遍历

二叉树是数据结构中很重要的一个章节，很多同学反应很难，今天我就把我平时的经验给大家讲解一下，今天讲一下二叉树的遍历工具/原料 ● 数据结构知识 ● 了解树的定义

爱被打了一巴掌/ 2022年05月10日 03:08/ 0 赞/ 299 阅读

相关 C - Tree UVA - 548

题目描述： You are to determine the value of the leaf node in a given binary tree that is

Love The Way You Lie/ 2022年03月22日 06:06/ 0 赞/ 120 阅读

相关二叉树遍历

//节点定义 template <class T> struct binaryTreeNode { T

比眉伴天荒/ 2022年03月19日 14:08/ 0 赞/ 332 阅读

相关 Tree UVA - 548 (DFS+建立二叉树)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgx

男娘i/ 2022年02月28日 13:22/ 0 赞/ 183 阅读