http://acm.hdu.edu.cn/showproblem.php?pid=1710
题意：已知前序和中序遍历求后序遍历
这道题目按照我一开始的方法我发现做不了。。。因为他肯定有数据是专门比如一直左子树的，我用数组像写线段树那样模拟二叉树是不可取的，毕竟2的10000次方，根本开不出来这样的数组。后来看了看，发现，啊啊啊啊啊？？？这根本不需要存在数组啊，直接输出就行啊，详情看代码。
代码如下：注释掉的部分就是我一开始打算先放进数组再取出来的做法，太蠢了。
#include<bits/stdc++.h> using namespace std; int front[1005], mid[1005], tree[100005], back[1005]; int cnt = 0, n; void build(int x, int fs, int fe, int ms, int me) { // cout << front[fs] << " " << fs <<" "<< fe <<" "<< ms <<" "<< me << endl; if(fs > fe) return; int root = ms; while(mid[root] != front[fs]) root++; if(root - ms >= 1) build(x * 2, fs + 1, fs + root - ms, ms, root - 1); if(ms + root - ms <= fe) build(x * 2 + 1, fs + root - ms + 1, fe , root + 1, me); printf("%d%c", front[fs], x == 1 ? '\n' : ' '); } void print(int x) { if(tree[x * 2] != -1) print(x * 2); if(tree[x * 2 + 1] != -1) print(x * 2 + 1); back[cnt++] = tree[x]; } int main() { while(cin >> n) { memset(tree, -1, sizeof(tree)); cnt = 0; for(int i = 0; i < n; i++) cin >> front[i]; for(int i = 0; i < n; i++) cin >> mid[i]; build(1, 0, n - 1, 0, n - 1); // print(1); // for(int i = 0; i < cnt; i++) // printf("%d%c", back[i], i == cnt - 1 ? '\n' : ' '); } return 0; }