根据先序遍历的结果还原二叉搜索树

又二叉树的特征，知道先序遍历的输出和中序遍历的输出，就可以还原一颗唯一的树。而在 二叉搜索树中，中序遍历恰恰是将先序遍历排序后的结果。所以给出先序遍历的输出结构，便可以 还原这棵二叉搜索树。

My Code

#include<iostream>
#include<stdio.h>
#include<vector>
#include<map>
#include<algorithm>
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 ns 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 !
}

备注 方法应该没错，都是规律，但是做题用到这个方法来还原二叉树时竟然有一般的数据超时了，小烦。 暂时未找到超时原因。。。