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

妖狐艹你老母 2022-08-07 05:56 199阅读 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 条评论，199人围观）

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

相关阅读

相关 S-Trees UVA712（二叉树）

题目读了半天，差点被吓住！题目本身很简单，就是一颗满二叉树，向左（2\temp）,向右（2\temp+1），最后减去（1<<n）-1;（即非叶子结点的个数，因为储存叶子结点是从

怼烎@/ 2024年02月17日 19:01/ 0 赞/ 44 阅读

相关 Tree UVA 548(DFS)

解题思路：对于给定的二叉树的中序遍历和后序遍历，可以构造出这棵二叉树，方法是根据后序遍历找到树根。然后在中序遍历中找到树根，从而找出左右子树的结点列表，然后递归构造左

我就是我/ 2024年02月17日 18:51/ 0 赞/ 40 阅读

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

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

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

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

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

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

相关【日常学习】【指针二叉树+BFS】Uva - 122 Trees on the level题解

作为一个传统型的树盲，不得不把树重新学习一次。通常我是不太喜欢指针的，但这样写下来感觉还能接受。题目来源是ACM DUKE 1993 Uva 122 杭电也有这道题这道

柔情只为你懂/ 2022年08月07日 04:51/ 0 赞/ 24 阅读

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

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

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

相关 uva122 二叉树的层次遍历

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

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

相关二叉树遍历

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

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

相关 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 赞/ 143 阅读

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgx

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