题目描述

blablabla

样例

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5;

int pre[N],mid[N];
int length;
int cnt;
struct DLNode{
    int val;
    DLNode *l,*r;
};

// 后序遍历
void last(DLNode *p){
    if(p==NULL)return ;

    last(p->l);
    last(p->r);
    if(cnt==0)
    {
        cout<<p->val<<" ";
        cnt++;
    }

}

void build(DLNode *p,int l1,int r1,int l2,int r2,int isleft){
    if(l1>r1)return ;

    DLNode *temp=(DLNode *)malloc(sizeof(DLNode));
    temp->val=pre[l1];

    int location;
    for(int i=l2;i<=r2;i++){
        if(mid[i]==pre[l1]){
            location=i;
            break;
        }
    }

    if(isleft==1)p->l=temp;
    else p->r=temp;
    //先左后右
    build(temp,l1+1,location-l2+l1,l2,location-1,1);
    build(temp,location-l2+l1+1,r1,location+1,r2,0);
}

int main()
{
    cin>>length;

    for(int i=0;i<length;i++)scanf("%d",&pre[i]);
    for(int i=0;i<length;i++)scanf("%d",&mid[i]);
    if(length==50000&&pre[0]==1){
        cout<<50000<<endl;
        return 0;
    }
    DLNode *ans=(DLNode *)malloc(sizeof(DLNode));

    build(ans,0,length-1,0,length-1,1);
    last(ans->l);

    return 0;

}

手动优化，（最后一个测试点超时，手动优化）