通过后根和中跟遍历，不断确定左右子树
// #pragma GCC optimize(2) #include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <cmath> #include <string> #include <vector> #include <stack> #include <map> #include <sstream> #include <cstring> #include <set> #include <cctype> #include <bitset> #define IO \ ios::sync_with_stdio(false); \ // cout.tie(0); using namespace std; // int dis[8][2] = {0, 1, 1, 0, 0, -1, -1, 0, 1, -1, 1, 1, -1, 1, -1, -1}; typedef unsigned long long ULL; typedef long long LL; typedef pair<int, int> P; const int maxn = 1e3 + 10; const int maxm = 2e5 + 10; const LL INF = 0x3f3f3f3f3f3f3f3f; const int inf = 0x3f3f3f3f; const LL mod = 1e9 + 7; const double pi = acos(-1); struct Node { int num; Node *left; Node *right; }; int n; int post[maxn]; int mid[maxn]; Node *creat(int postL, int postR, int midL, int midR) { if (postL > postR) return NULL; Node *T = new Node; T->num = post[postR]; int p; for (p = midL; p <= midR; p++) if (mid[p] == post[postR]) break; int numleft = p - midL; T->left = creat(postL, postL + numleft - 1, midL, p - 1); T->right = creat(postL + numleft, postR - 1, p + 1, midR); return T; } void Level(Node *root) { int flag = 0; queue<Node *> q; q.push(root); while (!q.empty()) { Node *a = q.front(); q.pop(); if (flag == 0) { cout << a->num; flag = 1; } else { cout << " " << a->num; } if (a->left) q.push(a->left); if (a->right) q.push(a->right); } return; } int main() { #ifdef WXY freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); #endif IO; cin >> n; for (int i = 0; i < n; i++) cin >> post[i]; for (int i = 0; i < n; i++) cin >> mid[i]; Node *T; T = creat(0, n - 1, 0, n - 1); Level(T); return 0; }
