首页 > 代码库 > UVA - 548 Tree(二叉树的递归遍历)
UVA - 548 Tree(二叉树的递归遍历)
题意:已知中序后序序列,求一个叶子到根路径上权和最小,如果多解,则叶子权值尽量小。
分析:已知中序后序建树,再dfs求从根到各叶子的权和比较大小
#include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<stack> #include<deque> #include<queue> #include<list> typedef long long ll; typedef unsigned long long llu; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const ll LL_INF = 0x3f3f3f3f3f3f3f3f; const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f; const int dr[] = {0, 0, -1, 1}; const int dc[] = {-1, 1, 0, 0}; const double pi = acos(-1.0); const double eps = 1e-8; const int MAXN = 10000 + 10; const int MAXT = 1000000 + 10; using namespace std; string a, b; vector<int> in_order, post_order; int leftchild[MAXN]; int rightchild[MAXN]; int anssum; int ansv; int build_tree(int L1, int R1, int L2, int R2){ if(L1 > R1) return 0; int root = post_order[R2]; int st = L1; while(in_order[st] != root) ++st; int cnt = st - L1;//一定要通过个数来控制取出来的中序后序序列的左右下标 leftchild[root] = build_tree(L1, st - 1, L2, L2 + cnt - 1);//值为root的左孩子结点的值,第四个参数不能写成st-1,因为取出来的相对应的中序和后序序列不一定是下标对齐的 rightchild[root] = build_tree(st + 1, R1, L2 + cnt, R2 - 1); return root; } void dfs(int root, int sum){ sum += root; if(!leftchild[root] && !rightchild[root]){//叶子 if(sum < anssum || (sum == anssum && root < ansv)){ anssum = sum; ansv = root; } } if(leftchild[root]){ dfs(leftchild[root], sum); } if(rightchild[root]){ dfs(rightchild[root], sum); } } int main(){ while(getline(cin, a)){ in_order.clear(); post_order.clear(); memset(leftchild, 0, sizeof leftchild); memset(rightchild, 0, sizeof rightchild); stringstream s1(a); int x; while(s1 >> x){ in_order.push_back(x); } getline(cin, b); stringstream s2(b); while(s2 >> x){ post_order.push_back(x); } int len = in_order.size(); build_tree(0, len - 1, 0, len - 1); int root = post_order[len - 1]; anssum = INT_M_INF; ansv = INT_M_INF; dfs(root, 0); printf("%d\n", ansv); } }
已知中序和后序可建树,建成后,可输出前序序列。
#include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<stack> #include<deque> #include<queue> #include<list> typedef long long ll; typedef unsigned long long llu; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const ll LL_INF = 0x3f3f3f3f3f3f3f3f; const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f; const int dr[] = {0, 0, -1, 1}; const int dc[] = {-1, 1, 0, 0}; const double pi = acos(-1.0); const double eps = 1e-8; const int MAXN = 10000 + 10; const int MAXT = 1000000 + 10; using namespace std; string a, b; vector<int> in_order, post_order, pre_order; int leftchild[MAXN]; int rightchild[MAXN]; int build_tree(int L1, int R1, int L2, int R2){ if(L1 > R1) return 0; int root = post_order[R2]; int st = L1; while(in_order[st] != root) ++st; int cnt = st - L1;//一定要通过个数来控制取出来的中序后序序列的左右下标 leftchild[root] = build_tree(L1, st - 1, L2, L2 + cnt - 1);//值为root的左孩子结点的值,第四个参数不能写成st-1,因为取出来的相对应的中序和后序序列不一定是下标对齐的 rightchild[root] = build_tree(st + 1, R1, L2 + cnt, R2 - 1); return root; } void dfs(int root){ pre_order.push_back(root); if(leftchild[root]){ dfs(leftchild[root]); } if(rightchild[root]){ dfs(rightchild[root]); } } int main(){ while(getline(cin, a)){ in_order.clear(); post_order.clear(); pre_order.clear(); memset(leftchild, 0, sizeof leftchild); memset(rightchild, 0, sizeof rightchild); stringstream s1(a); int x; while(s1 >> x){ in_order.push_back(x); } getline(cin, b); stringstream s2(b); while(s2 >> x){ post_order.push_back(x); } int len = in_order.size(); build_tree(0, len - 1, 0, len - 1); int root = post_order[len - 1]; dfs(root); for(int i = 0; i < len; ++i){ if(i) printf(" "); printf("%d", pre_order[i]); } printf("\n"); } }
UVA - 548 Tree(二叉树的递归遍历)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。