先建树,然后遍历数组。
这种方式比较消耗空间,适用于数据量小的情况,如果形成一条链,那将是致命的这个空间。
#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;
}