Acwing - 1497. 树的遍历

Solost

2023 年 03 月 16 日

212 次浏览

暂无评论

2202字数

ACM笔记题目题解

![image(1).png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F03%2F16%2Fimage%281%29.png)

## 题目链接

[题目链接](https://www.acwing.com/problem/content/1499/)

## solution

![E24B2DA983D0779AC64D62EBD55B3948.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F03%2F16%2FE24B2DA983D0779AC64D62EBD55B3948.png)

由于给出的是后序遍历与中序遍历，后续遍历的遍历顺序是左右根，中序遍历的顺序是根左右，所以我们先用后序遍历确定根节点，然后再在中序遍历里面找到该节点，然后该节点左边就是左子树，右边就是右子树，左子树的数量就是`k - bl + 1`,那么对应到后序遍历里面就是`al - (k - bl + 1) == al - k + bl - 1`,然后再处理右子树，就是后序`al - k + bl`到`ar - 1`，中序`k + 1`到`br`，不断dfs即可

### 不用DFS版本

```cpp
#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版本

```cpp
#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;
}
```

最后修改：2023 年 03 月 16 日