먼저 훑어본 결과에 따라 두 갈래 검색 트리 복원

또 두 갈래 나무의 특징은 먼저 흐르는 출력과 중간 흐르는 출력을 알면 유일한 나무를 복원할 수 있다는 것이다.두 갈래 검색 트리에서 중차 반복은 바로 먼저 정렬된 결과입니다.그래서 먼저 훑어보는 출력 구조를 제시하면 이 두 갈래 검색 트리를 복원할 수 있다.
My Code

#include
#include
#include
#include
#include
using namespace std;

const int maxn = 1009;
int pre[maxn];	//preorder
int mid[maxn];	//indorder
map<int,int> index; //index of value maxn in mid[]

//define the node of tree
struct Node{
	int val;
	Node *ls, *rs;
	Node(){ ls = rs = NULL, val = -1; }
};
//use recursino to rebuild an binary find tree
//lr and rr mean the index of node in mid[] that it node cover by indirectly 
//pi mean the index of value in pre[] that node n's value should be set
void build(Node *&n,int pi, int lr, int rr){	
	if(n==NULL) n = new Node();
	int v = pre[pi];
	n->val =v;
	//cout << v << endl;
	if (rr - lr < 1) return; //prove that it node is leaf
	int mi = index[v];
	if (mid[mi + 1] == mid[mi]) index[v]++;
	if (mi - lr > 0){	//then it node have left son
		build(n->ls, pi + 1, lr, mi - 1);	//left son value is just in the right of it node in pre[]
	}
	if (rr - mi > 0){ //it node have right son
		int dis = mi - lr + 1;	//the distant of index between it node and right son in pre[]
		build(n->rs, pi+dis, mi + 1, rr);
	}
}

int main(){
	int n;
	//get input data
	cin >> n;
	for (int i = 0; i < n; i++){
		scanf("%d", &pre[i]);
		mid[i] = pre[i];
	}
	//handle the data
	sort(mid, mid + n);
	for (int i = n - 1; i >= 0; i--){
		index[mid[i]] = i;	//recorde the index of value that appare in first times
	}
	//rebuild binary search tree by the data we have
	Node *head = NULL;
	build(head, 0, 0, n-1);//not include n !
}

비고 방법은 틀림없을 것이다. 모두 규칙이다. 그러나 문제를 풀 때 이 방법으로 두 갈래 나무를 복원할 때 뜻밖에도 일반적인 데이터가 시간을 초과했다. 귀찮아.당분간 시간 초과 원인을 찾지 못했습니다...