树的遍历（待写）

给定中序和其他一种遍历的序列可以确定一颗二叉树的结构。

#include <bits/stdc++.h>

using namespace std;

const int N = 35;

int n;
int a[N], b[N], p[N];
vector<int> level[N];

// al:a数组的左端点
// bl:b数组的左端点
// d：层数
void build(int al, int ar, int bl, int br, int d)
{
    if (al > ar) return;
    // 取a数组的右端点 也就是当前树的根节点。
    int val = a[ar];
    // 这里因为先遍历的左子树，然后遍历的右子树，进入递归了它的深度会加1，
    // 但是当遍历同深度的右子树的时候，它的深度就又回来了。
    level[d].push_back(val);
    // 找到根节点再中序数组中的位置。
    int k = p[val];
    // 先遍历左子树
    build(al, al + k - 1 - bl, bl, k - 1, d + 1);
    // 然后遍历右子树
    build(al + k - bl, ar - 1, k + 1, br, d + 1);
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    for (int i = 0; i < n; i ++ ) cin >> b[i];

    // 这是为了方便从后序中的根节点快捷的找到中序数组中的位置。注意里面是中序遍历的数组。
    for (int i = 0; i < n; i ++ ) p[b[i]] = i;

    build(0, n - 1, 0, n - 1, 0);

    for (int i = 0; i < n; i ++ )
        for (int x : level[i])
            cout << x << ' ';

    return 0;
}