【1138】Postorder Traversal (25 分)

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;  
//后序遍历，找到第一个元素就退出
//此题不要前序中序建立树再遍历树(可能超时)
const int maxn=50010;
int n,m,p,t,pre[maxn],in[maxn];
bool flag=false; 
void getpost(int preL,int preR,int inL,int inR){
  if(preL>preR || flag==true)  return ;
    //flag==true去掉虽然能ac，可能超时
  int k;
  for(k=inL;k<=inR;k++){
    if(in[k] == pre[preL]) {  //在中序序列中找到相等的结点
      break;
    }
  }
  int numLeft=k-inL; //左子树的结点个数
  getpost(preL+1,preL+numLeft,inL,k-1);
  getpost(preL+numLeft+1,preR,k+1,inR);
  if(flag == false){
    flag=true;
    printf("%d",pre[preL]);
  }
}
int main(){   
  int n;
  scanf("%d",&n);
  for(int i=0;i<n;i++)  scanf("%d",&pre[i]);
  for(int i=0;i<n;i++)  scanf("%d",&in[i]);
  getpost(0,n-1,0,n-1);  
  system("pause"); 
    return 0;   
}