题目描述

根据前序序列和中序序列构建二叉树

算法1

C++ 代码

#include<iostream>
#include<map>
using namespace std;
typedef long long LL;
const int N=50010;
LL preorder[N],midorder[N],postorder[N];

map<int,int> l,r;
int n;
int k=0;
map<int,int> position;

int build(int ml,int mr,int pl,int pr){

    LL root=preorder[pl];
    int k=position[root];

    if(k>ml){
        l[root]=build(ml,k-1,pl+1,pl+1+k-1-ml);
    }
    if(k<mr){
        r[root]=build(k+1,mr,pl+1+k-1-ml+1,pr);
    }
    return root;
}

void trave(int root){
    if(!root){return ;}
    if(l[root]){
        trave(l[root]);
    }
    if(r[root]){
        trave(r[root]);
    }
    postorder[k++]=root;
    return ;
}

int main(){
    cin>>n;

    for(int i=0;i<n;i++){
        cin>>preorder[i];
    }
    for(int i=0;i<n;i++){
        cin>>midorder[i];
        position[midorder[i]]=i;
    }

    int root=build(0,n-1,0,n-1);
    trave(root);
    cout<<postorder[0]<<endl;

    return 0;
}