Construct Binary Tree from Preorder and Inorder Traversal (LeetCode Array)

Question:  Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

Idea: From the preorder traversal, we can know the root of the tree. Then we find the root in the inorder traversal, assumes the root position is at index x. Split the inorder traversal into two arrays: (start->x-1) and (x+1->end). The first array is the left substree of root, the second array is the right substree of root. Then construct substrees recursively on the two substrings.

The above is the basic idea. During the implementation, in order to avoid copying the whole string during the split, we only pass the index, e.g. start->x-1, x+1->end.

Time: O(n^2) (find root position in inorder is O(n), for n tree nodes)
Space: O(lgn)

Code: 

 public class Solution {  
   public int preIndex;  
   public TreeNode buildTree(int[] preorder, int[] inorder) {  
     preIndex=0;  
     return buildRec(preorder,inorder,0,inorder.length-1);  
   }  
   public TreeNode buildRec(int[] preorder,int[] inorder,int inStart,int inEnd)  
   {  
     if(inStart>inEnd)  
       return null;  
     TreeNode root=new TreeNode(preorder[preIndex]);  
     preIndex+=1;  
     int splitPos=findIndex(inorder,inStart,inEnd,root.val);  
     root.left=buildRec(preorder,inorder,inStart,splitPos-1);  
     root.right=buildRec(preorder,inorder,splitPos+1,inEnd);  
     return root;  
   }  
   public int findIndex(int[] arr, int start, int end,int target)  
   {  
     for(int i=start;i<=end;i++)  
     {  
       if(arr[i]==target)  
         return i;  
     }  
     return -1;  
   }  
 }