1020. Tree Traversals (25)

//给定后序和中序遍历 要求输出层序遍历
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 31;
int n;
struct node { int data; node *l, *r;};
vector<int> post(maxn), in(maxn), level;
node *build(int postL, int postR, int inL, int inR){
    if(postL > postR) return NULL;
    node *root = new node;
    root->data = post[postR];
    int k;
    for (k = inL; k <= inR; k++)
        if(in[k] == post[postR]) break;
    int leftnum = k - inL;
    root->l = build(postL, postL + leftnum - 1, inL, k - 1);
    root->r = build(postL + leftnum, postR - 1, k + 1, inR);
    return root;
}
void bfs(node *root){
    queue<node*> q;
    q.push(root);
    while (!q.empty()) {
        node *now = q.front();
        q.pop();
        level.push_back(now->data);
        if(now->l) q.push(now->l);
        if(now->r) q.push(now->r);
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> post[i];
    for(int i = 0; i < n; i++) cin >> in[i];
    node *root = build(0, n-1, 0, n-1);
    bfs(root);
    for (int i = 0; i < level.size(); i++)
        printf("%d%c", level[i], i == (int)level.size() - 1 ? '\n' : ' ');

    return 0;
}