首页 > 代码库 > 洛谷P1827 美国血统 American Heritage
洛谷P1827 美国血统 American Heritage
P1827 美国血统 American Heritage
- 54通过
- 90提交
- 题目提供者JOHNKRAM
- 标签USACO
- 难度普及-
讨论 题解
最新讨论
- 暂时没有讨论
题目描述
农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛 们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而 不是用图形的方法。
你的任务是在被给予奶牛家谱的“树中序遍历”和“树前序遍历”的符号后，创建奶牛家谱的“树的 后序遍历”的符号。每一头奶牛的姓名被译为一个唯一的字母。（你可能已经知道你可以在知道树的两 种遍历以后可以经常地重建这棵树。）显然，这里的树不会有多于 26 个的顶点。 这是在样例输入和 样例输出中的树的图形表达方式：
树的中序遍历是按照左子树，根，右子树的顺序访问节点。
树的前序遍历是按照根，左子树，右子树的顺序访问节点。
树的后序遍历是按照左子树，右子树，根的顺序访问节点。
输入输出格式
输入格式：
第一行： 树的中序遍历
第二行： 同样的树的前序遍历
输出格式：
单独的一行表示该树的后序遍历。
输入输出样例
输入样例#1：
ABEDFCHGCBADEFGH
输出样例#1：
AEFDBHGC
说明
题目翻译来自NOCOW。
USACO Training Section 3.4
分析：比较基础的数据结构题，前序遍历的第一个节点就是根，在中序遍历中找到他，其左边的就是左子树，右边的就是右子树，递归进行这个操作即可.
#include <cstdio>#include <string>#include <map>#include <cstring>#include <iostream>#include <algorithm>using namespace std;string a, b;char lc[1000], rc[1000];char build(int l, int r, int x, int y){ if (l > r) return 0; int p = l; while (a[p] != b[x]) p++; int t = p - l; lc[b[x]] = build(l, p - 1, x + 1, x + t); rc[b[x]] = build(p + 1, r, x + t + 1, y); return b[x];}void dfs(char x){ if (lc[x]) dfs(lc[x]); if (rc[x]) dfs(rc[x]); printf("%c", x);}void solve(){ build(0, a.size() - 1, 0, a.size() - 1); int root = b[0]; dfs(root);}int main(){ cin >> a >> b; solve(); //while (1); return 0;}
洛谷P1827 美国血统 American Heritage
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。