写在前面
树的遍历问题对于我这种刚入门ACM的蒟蒻还是算比较难的了,很多思路没法从之前普通的题型转移过来
需要多多练习和吸收,加油!
UVA 548 Tree
题目链接:https://www.luogu.com.cn/problem/UVA548
思路:
1.根据中序遍历和后序遍历建树(重点)
2.对已经建好的树,进行dfs遍历,到了叶子结点判断满不满足路程最短(或者路程和最短相同但是叶子结点更小)
3.输出路程最短的叶子结点(有多个最短路程的叶子结点就输出叶子结点最小的那一个)
代码:
1.根据中序遍历和后序遍历建树
如何建树:hhttps://blog.csdn.net/liitdar/article/details/82598039?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase
int build_tree(int l,int r,int l2,int r2)//l,r指中序遍历左右边界,l2,r2指后序遍历边界 { if (l > r) return 0; int root = post[r2]; int p = l; while (in[p] != root) p++; int cnt = p - l; ltr[root]=build_tree(l, p - 1, l2, l2 + cnt - 1); rtr[root]=build_tree(p + 1, r, l2 + cnt, r2 - 1); return root; }
2.对已经建好的树,进行dfs遍历,到了叶子结点判断满不满足路程最短(或者路程和最短相同但是叶子结点更小)
void dfs(int s,int num)//s是当前根的值,num是到这根的路程 { num += s; if (ltr[s] == 0 && rtr[s] == 0)//是叶子节点 { if (num < mini||(num==mini&&imini>s)) { mini = num; imini = s; } } else { if (ltr[s] != 0) dfs(ltr[s], num); if (rtr[s] != 0) dfs(rtr[s], num); } }
3.完整代码
#include <iostream> #include <string> #include <algorithm> #include <cstring> #include<sstream> using namespace std; int in[10100],post[10100],ltr[10100],rtr[10100]; int n; bool iread(int *a) { string line; if (!getline(cin, line)) return false; stringstream ss(line); n = 0; int x; while (ss >> x) { n++; a[n] = x; } return 1; } int build_tree(int l,int r,int l2,int r2) { if (l > r) return 0; int root = post[r2]; int p = l; while (in[p] != root) p++; int cnt = p - l; ltr[root]=build_tree(l, p - 1, l2, l2 + cnt - 1); rtr[root]=build_tree(p + 1, r, l2 + cnt, r2 - 1); return root; } int num = 0, mini = 1001000,imini=1001000; void dfs(int s,int num) { num += s; if (ltr[s] == 0 && rtr[s] == 0) { if (num < mini||(num==mini&&imini>s)) { mini = num; imini = s; } } else { if (ltr[s] != 0) dfs(ltr[s], num); if (rtr[s] != 0) dfs(rtr[s], num); } } int main() { string s; while (iread(in)) { iread(post); build_tree(1,n,1,n); num = 0; dfs(post[n],num); cout << imini << endl; memset(in, 0, sizeof(in)); memset(post, 0, sizeof(post)); memset(ltr, 0, sizeof(ltr)); memset(rtr, 0, sizeof(rtr)); num = 0; mini = 1001000; imini = 1001000; } return 0; }
反思:
这道题中的 输入 和 已知后序遍历和中序遍历建树 非常值得学习,输入利用了sstream,很方便的解决了问题。