树的遍历 1499

二叉树 #哈希

1497. 树的遍历 - AcWing题库

一个二叉树，树中每个节点的权值互不相同。

现在给出它的后序遍历和中序遍历，请你输出它的层序遍历。

输入格式

第一行包含整数 N，表示二叉树的节点数。

第二行包含 N 个整数，表示二叉树的后序遍历。

第三行包含 N 个整数，表示二叉树的中序遍历。

输出格式

输出一行 N 个整数，表示二叉树的层序遍历。

数据范围

1≤N≤30,
官方并未给出各节点权值的取值范围，为方便起见，在本网站范围取为 1∼N。

输入样例：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

4 1 6 3 5 7 2

#include <bits/stdc++.h>

#define x first
#define y second
#define IOS                           \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);
#define read(x) scanf("%lld", &x)

using namespace std;
typedef pair<int, int> PII;
typedef long long LL;

const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;
const int K = 1e3 + 10;

int a[N];
int b[N];
int tr[N];

unordered_map<int, int> l, r, pos;

int build(int al, int ar, int bl, int br)
{
    int root = a[ar];

    int k = pos[root]; // K 是 root 在中序的位置
    // 每次划分后 后序树的左右树也会有与中序树相对应的区间范围
    // 存在左子树
    if (bl < k)
    {
        l[root] = build(al, al + ((k - 1) - bl), bl, k - 1);
    }
    // 存在右子树
    if (br > k)
    {
        r[root] = build(al + ((k - 1) - bl + 1), ar - 1, k + 1, br);
    }
    return root;
}

void bfs(int root)
{
    queue<int> q;
    q.push(root);
    while (q.size())
    {
        int t = q.front();
        q.pop();
        cout << t << " ";

        if (l.count(t))
            q.push(l[t]);
        if (r.count(t))
            q.push(r[t]);
    }
}

int main()
{
    IOS;

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
        pos[b[i]] = i;
    }

    int root = build(1, n, 1, n);
    bfs(root);

    return 0;
}