首页 > 代码库 > UVA548 Tree

UVA548 Tree

2024-08-16 08:37:00   217人阅读

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

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

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

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

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

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

总之，递归很强大很强大！

#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


联系
我们