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

UVA 548 树 递归典型

程序员文章站 2022-03-13 20:48:23
...

题目链接

题目大意(翻译):

给定一颗节点带权的二叉树的中序遍历序列和后序遍历序列,要求找出叶子节点中到根的路径上的权和最小的节点。
注:
1. 所有节点的权值都不同

2. 如果权和最小的叶子节点有多个,输出其中权值最小的。

题目思路:

  1. 首先根据后序遍历序列和中序遍历序列构建该二叉树。
  2. 从根节点进行DFS遍历整棵树,找到符合条件的叶子节点。

UVA 548 树 递归典型

代码如下:

#include <iostream>
#include <sstream>
#include <string>
using namespace std;

const int maxn = 10000+10;
int in_order[maxn],post_order[maxn],lch[maxn],rch[maxn];	// 使用两个数组构建二叉树 

int n,best,best_sum;

bool read_list(int *a)
{
	string s;
	if(!getline(cin,s)) return false;
	stringstream ss(s);
	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;
	int root = post_order[R2];
	int p = L1;
	while(in_order[p]!=root) p++;
	int cnt = p-L1;
	lch[root] = build(L1,p-1,L2,L2+cnt-1);
	rch[root] = build(p+1,R1,L2+cnt,R2-1);
	return root;
}

void dfs(int v,int sum)
{
	sum += v; 
	if(!lch[v] && !rch[v]) {	// 叶子节点 
		if(sum < best_sum || (sum==best_sum && v < best)) {
			best = v; best_sum = sum;
		}
	}
	if(lch[v]) dfs(lch[v],sum);
	if(rch[v]) dfs(rch[v],sum);
}

int main()
{
	while(read_list(in_order)) {
		read_list(post_order);
		build(0,n-1,0,n-1);
		best_sum = 1 << 30;
		dfs(post_order[n-1],0);
		cout << best << endl;
	}
	return 0;
}
相关标签: UVA