首页 > 代码库 > UVA548 Tree

UVA548 Tree

从这个题目我们再次学习到了一个知识点,就是递归函数的强大!

首先,我们先明确一个知识点,就是你知道了一棵树的中序和后序遍历,求他的前序遍历,我们应该怎么来做?

第一步:最初的时候,我们的后序遍历的最后一个数字就是我们的一个子树的根节点

第二步:找到我们的根结点后,跟据我们中序遍历的性质,我们的树就会被自然地分成了左右两个部分。

第三步:统计出来左右两个子树的大小和长度,这样就能继续重复上面的步骤

这道题的读写输入也是一个知识点,这个我是直接看的刘汝佳的知识点来做的。

总之,递归很强大很强大!

#include <iostream>#include <string>#include <sstream>#include <algorithm>#include <stdio.h>using namespace std;const int maxn = 10000+10;const int INF = 1e9;int in_order[maxn], post_order[maxn];int n;int lch[maxn], rch[maxn];int index,maxx;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_tree(int L1, int R1, int L2, int R2){	if(L1 > R1)		return 0;	int p = L1;	int root = post_order[R2];	while(in_order[p] != root)		p++;	int cnt = p - L1;	//本题目的核心其实就是这两步,这两步一定要好好地思考一下,就是递归在建树这里的运用	//怎么去理解我传递的参数?不要去理解成什么长度了,只要理解成数组的起始和终止坐标就好	lch[root] = build_tree(L1, p - 1, L2, L2 + cnt-1);	rch[root] = build_tree(p+1, R1, L2+cnt,R2-1);	return root;}void dfs(int root, int sum){	sum += root;	if(!lch[root] && !rch[root])	{		if(sum < maxx || (sum == maxx && root < index))		{			maxx = sum;			index = root;		}	}	if(lch[root])		dfs(lch[root], sum);	if(rch[root])		dfs(rch[root], sum);}int main(){	while(read_list(in_order))	{		read_list(post_order);		//int len = n - 1; // 最后一个数字的下标,长度的话就是n		int root = build_tree(0,n-1,0,n-1);		//printf("%d\n", root);		maxx = INF;				index = root;		dfs(root, 0);		printf("%d\n", index);	}	return 0;}

  

UVA548 Tree