L2-006 树的遍历

先建树，然后遍历数组。
这种方式比较消耗空间，适用于数据量小的情况，如果形成一条链，那将是致命的这个空间。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int in[N], post[N];
vector<int> tree(N,-1); 
void build(int root, int start, int ed, int idx) {
	if (start > ed) return;
	int i;
	for (i = start; i <= ed; i++) {
		if (in[i] == post[root]) {
			break;
		}
	}
   tree[idx] = post[root];
	build(root - ed + i - 1, start, i - 1, 2 * idx);//左
	build(root - 1, i + 1, ed, 2 * idx + 1);//右
}
int main() {
	int ssize;
	cin >> ssize;
	for (int i = 0; i < ssize; i++) {
		cin >> post[i];
	}
	for (int i = 0; i < ssize; i++) {
		cin >> in[i];
	}
	build(ssize - 1, 0, ssize - 1, 1);
	int flag = 0;
	for (int i = 1; i < tree.size(); i++) {
		if (tree[i] != -1) {
           if(flag) cout << " ";
            cout << tree[i];
            flag++;
		}
	}
	return 0;
}