【LSP】c_pat_由后序遍历和中序遍历确定层序遍历（利用性质

无名

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

思路
#include<bits/stdc++.h>
using namespace std;
const int N=35;
int n, post[N], in[N];
unordered_map<int, int> mp;
struct node {
    int val;
    node *left, *right;
};
node* dfs(int inL, int inR, int postL, int postR) {
    if (postL>postR) return NULL;
    int k=mp[post[postR]], lsz=k-inL;
    node* root=new node();
    root->val=post[postR];
    root->left=dfs(inL, k-1, postL, postL+lsz-1);
    root->right=dfs(k+1, inR, postL+lsz, postR-1);
    return root;
}
void bfs(node* root) {
    queue<node*> q; q.push(root);
    int c=0;
    while (!q.empty()) {
        for (int i=q.size(); i>0; i--) {
            auto now=q.front(); q.pop();
            cout<<now->val;
            if (c++!=n-1) cout<<' ';
            if (now->left!=NULL)  q.push(now->left);
            if (now->right!=NULL) q.push(now->right);
        }
    }
}
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n;
    for (int i=0; i<n; i++) cin>>post;
    for (int i=0; i<n; i++) cin>>in, mp[in]=i;;
    bfs(dfs(0, n-1, 0, n-1));
    return 0;
}