题目链接
solution
由于给出的是后序遍历与中序遍历,后续遍历的遍历顺序是左右根,中序遍历的顺序是根左右,所以我们先用后序遍历确定根节点,然后再在中序遍历里面找到该节点,然后该节点左边就是左子树,右边就是右子树,左子树的数量就是k - bl + 1
,那么对应到后序遍历里面就是al - (k - bl + 1) == al - k + bl - 1
,然后再处理右子树,就是后序al - k + bl
到ar - 1
,中序k + 1
到br
,不断dfs即可
不用DFS版本
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
int a[N], b[N], p[N];
vector<int> level[N];
void build(int al, int ar, int bl, int br, int d)
{
if (al > ar)
return;
int root = a[ar];
int k = p[root];
level[d].push_back(root);
build(al, al + k - bl - 1, bl, k - 1, d + 1);
build(al + k - bl, ar - 1, k + 1, br, d + 1);
}
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++) {
cin >> b[i];
p[b[i]] = i;
}
build(1, n, 1, n, 1);
for (int i = 1; i <= n; i++) {
for (auto x : level[i]) {
cout << x << " ";
}
}
}
int main()
{
// IOS;
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
DFS版本
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<fstream>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
int n, a[N], b[N], p[N], l[N], r[N];
vector<int> level[N];
int build(int al, int ar, int bl, int br, int d){
if(al > ar) return 0;
int root = a[ar];
int k = p[root];
// level[d].push_back(root);
l[root] = build(al, al + k - bl - 1, bl, k - 1, d + 1);
r[root] = build(al + k - bl, ar - 1, k + 1, br, d + 1);
return root;
}
void bfs(){
queue<int> q;
q.push(a[n]);
while(q.size()){
auto t = q.front();
q.pop();
cout << t << " ";
if(l[t]) q.push(l[t]);
if(r[t]) q.push(r[t]);
}
}
void solve(){
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
cin >> b[i];
p[b[i]] = i;
}
build(1, n, 1, n, 1);
bfs();
}
int main(){
// IOS;
int t = 1;
// cin >> t;
while(t--){
solve();
}
return 0;
}