# My recursion solution,using map to optimize running time

• I save inorder position in a map,instead of searching every time.
I have reduce running time.

first solution takes 196 ms.
second takes 116 ms.

``````class Solution {
public:
vector<int> pre;
vector<int> in;
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
if(preorder.empty()||inorder.empty())return NULL;
pre = preorder;
in = inorder;
TreeNode *res  = buildTree(0,0,inorder.size()-1);
return res;
}
//prepos is position in preorder, inst is start position in inorder,inend is end in inorder
TreeNode *buildTree(int prepos,int inst,int inend){
if(inst>inend)return NULL;
TreeNode *res = new TreeNode(pre[prepos]);
int inpos = inst;
for(int i=inst;i<=inend;i++)//searching every time
if(in[i]==pre[prepos]){
inpos=i;
break;
}
res->left = buildTree(prepos+1,inst,inpos-1);
res->right = buildTree(prepos+(inpos-inst)+1,inpos+1,inend);
return res;
}

};
``````

second takes 116 ms.

``````class Solution {
public:
vector<int> pre;
vector<int> in;
map<int,int> inorderPos;
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
if(preorder.empty()||inorder.empty())return NULL;
for(int i=0;i<inorder.size();i++)
inorderPos[inorder[i]]=i;
pre = preorder;
in = inorder;
TreeNode *res  = buildTree(0,0,inorder.size()-1);
return res;
}

TreeNode *buildTree(int prepos,int inst,int inend){
if(inst>inend)return NULL;
TreeNode *res = new TreeNode(pre[prepos]);
int inpos = inorderPos[pre[prepos]];
res->left = buildTree(prepos+1,inst,inpos-1);
res->right = buildTree(prepos+(inpos-inst)+1,inpos+1,inend);
return res;
}

};``````

• Hello there~
I think my algorithm is the same as yours.But i got an TLE when i use java to write the code.

``````public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length == 0)
return null;
Map<Integer , Integer> map = new HashMap<Integer, Integer>();
for(int i = 0 ; i < inorder.length ; i++){
map.put(inorder[i],i);
}
return build(inorder,preorder,map,0,0,inorder.length-1);
}

public TreeNode build(int[] inorder , int[] preorder , Map<Integer , Integer> map ,int pos ,int start , int end ){
if(pos >= preorder.length)
return null;
int rootVal = preorder[pos];
if(end == start){
TreeNode root = new TreeNode(rootVal);
return root;
}
int inPos = map.get(rootVal);
TreeNode root = new TreeNode(rootVal);
root.left = build(inorder , preorder , map , pos+1 , start , inPos-1);
root.right = build(inorder , preorder , map , pos+(inPos-start)+1 , inPos+1 , end);
return root;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.