题目 二叉树 中序和后序还原

题目描述

https://www.acwing.com/problem/content/1499/

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long

int postorder[10010];
int inorder[10010];
int postpos[10010];
int inpos[10010];
int l[10010];
int r[10010];
int n;

int root;

void build(int il,int ir,int rt){
    int inrtpos=inpos[rt];
    int postrtpos=postpos[rt];

//  printf("%d\n",rt);
    //Right side:
    int rsize=ir-inrtpos;
    if(rsize>0){
        r[rt]=postorder[postrtpos-1];
        build(inrtpos+1,ir,r[rt]);
    }
    //Left side:
    int lsize=inrtpos-il;
    if(lsize>0){
        l[rt]=postorder[postrtpos-rsize-1];
        build(il,inrtpos-1,l[rt]);
    }
    return ;
}

void bfs(int root){
    queue<int> q;
    q.push(root);
    while(!q.empty()){
        int cur=q.front() ;
        q.pop();
        printf("%d ",cur);
        if(l[cur]){
            q.push(l[cur]);
        }
        if(r[cur]){
            q.push(r[cur] );
        }
    }
    return ;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&postorder[i]);
        postpos[postorder[i]]=i;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&inorder[i]);
        inpos[inorder[i]]=i;
    }
    root=postorder[n];
    build(1,n,root);
    bfs(root);
    return 0;
}