首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。