思路：

由后序遍历和中序遍历还原一棵树。我们都知道后序遍历是 左儿子->右儿子->父节点的顺序，那么后序遍历序列的最后一个一定是根节点 $root$，因此我们在中序遍历序列中找到这个 $root$ 就可以区分 $root$ 的左右子树了。后序遍历的倒数第二个一定是右子树的根节点（如果右子树存在的话），因此我们可以递归地进行上述过程，直到把整棵数还原出来为止。

题目要求我们输出层序遍历的结果，我们在递归的时候记录每个 $root$ 在第几层，将它放进对应层数的 $vector$ 即可。

这个图是由层数遍历还原子树的过程，和这里的题差不多hh。

类似的题还有：POJ2255

代码

#include <iostream>
#include <vector>
#define endl "\n"
using namespace std;

const int N = 32;
int n;
int pos[N], in[N];
vector<int> v[N];

void work(int pos[], int in[], int len, int u)
{
    if(!len) return;
    int root = pos[0], idx = 0;
    for(int i = 0; i < len; i++) 
    {
        if(in[i] == root)
        {
            idx = i;
            break;
        }
    }
    v[u].push_back(root);
    //左子树
    work(pos - 1 - (len - 1 - idx), in, idx, u + 1);
    //右子树
    work(pos - 1, in + idx + 1, len - 1 - idx, u + 1);
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++) cin >> pos[i];
    for(int i = 0; i < n; i++) cin >> in[i];
    work(pos + n - 1, in, n, 0);
    for(int i = 0; i < 32; i++)
    {
        if(!v[i].size()) continue;
        for(int j = 0; j < v[i].size(); j++)
            cout << v[i][j] << ' ';
    }
    return 0;
}