试题 算法训练 绘制地图
问题描述
最近，WYF正准备参观他的点卡工厂。WYF集团的经理氰垃圾需要帮助WYF设计参“观”路线。现在，氰垃圾知道一下几件事情：
1.WYF的点卡工厂构成一颗二叉树。
2.一共有n座工厂。
3.他需要把这颗树上的点以后序遍历的方法列出来，才能绘制地图。
还好，最近他的属下给了他先序遍历和中序遍历的数据。可是，氰垃圾最近还要帮㊎澤穻解决一些问题，没有时间。请你帮帮他，替他完成这项任务。由于氰垃圾的一些特殊的要求，WYF的参观路线将会是这棵树的后序遍历。
输入格式
第一行一个整数n，表示一共又n座工厂。
第二行n个整数，表示先序遍历。
第三行n个整数，表示中序遍历。
输出格式
输出共一行，包含n个整数，为后序遍历。
样例输入
8
1 2 4 5 7 3 6 8
4 2 7 5 1 8 6 3
样例输出
4 7 5 2 8 6 3 1
数据规模和约定
0<n<100000,。保证先序遍历和中序遍历合法，且均为1～n。
题解
题目意思很简单，就是已知二叉树先序和中序求后序。我看了网上大部分的解法，都需要建立二叉树，太复杂了，一定会超时。这种方法使用递归直接输出后序序列。详见代码注释。
#include <cstdio> #include <iostream> using namespace std; int pre[100000], in[100000]; int t = 0; void getpst(int *pre, int *in, int n) { if(n == 0) return; int root = pre[0]; int i; for(i = 0; i < n; i++) { if(in[i] == root)//在中序序列中找到根节点 break; } //递归找左子树，+1表示跳过根节点 getpst(pre + 1,in,i); //递归找右子树，+i表示跳过先序遍历中左子树的部分 getpst(pre + i + 1, in + i + 1, n - i - 1); t++; //这一步输出有一点难以理解，我们是按根左右递归下去，所以最后回来时是左右根刚好是后序遍历。 if(t == 1) cout << root; else cout << ' ' << root; return; } int main() { int n; cin >> n; int i; for(i = 0; i < n; i++)//输入先序数列 scanf("%d", &pre[i]); for(i = 0; i < n; i++) scanf("%d", &in[i]);//输入中序数列 getpst(pre, in, n); printf("\n"); return 0; }
