Leetcode -- 105. Construct Binary Tree from Preorder and Inorder Traversal

105. Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

思路：
pre: 1,2,3,4 //pre+1 can be left child, find its position 'rindex' in inorder
in:   4,2,1,3//[inStart, inEnd] is the range for left/right child
                     [inStart, rindex-1] - left child
                     [rindex+1, inEnd] - right child
                    **rindex+1 is right child, convert its position in preorder: preStart+rindex-inStart+1

Complexity:  Time O(n^2) Space O(1)
or use HashMap to improve find:  Time O(N) Space O(N)

var buildTree = function(preorder, inorder) {
    return helper(preorder, inorder, 0, inorder.length - 1, 0);
};
function helper(preorder, inorder, inStart, inEnd, preStart){
    if(preStart > inorder.length-1 || inStart > inEnd)
        return null;
    var root = new TreeNode(preorder[preStart]);
    var rindex = 0;
    for(var i = inStart; i <= inEnd; i++){
        if(inorder[i] === preorder[preStart]){
            rindex = i;
            break;
        }
    }
    root.left = helper(preorder, inorder, inStart, rindex-1, preStart+1);
    root.right = helper(preorder, inorder, rindex+1, inEnd,  preStart+rindex-inStart+1);
    return root;
}