Cacher is the code snippet organizer for pro developers

# In this solution, we use lenLeft to determine the left/right nodes in preorder,
# Rather than traverse it sequentially.


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if len(inorder) == 0:
            return None
        self.inDict = {}
        for index,each in enumerate(inorder):
            self.inDict[each] = index
        # self.preIndex = 0
        return self.build(inorder, 0, len(inorder) - 1, preorder, 0, len(preorder)-1)
    def build(self, inorder, inStart, inEnd, preorder, preStart, preEnd):
        if inStart > inEnd:
            return None
        curVal = preorder[preStart]
        curInIndex = self.inDict[curVal]
        leftLen = curInIndex - inStart
        curNode = TreeNode(curVal)
        # self.preIndex += 1
        curNode.left = self.build(inorder,  inStart,      curInIndex-1, preorder, preStart+1,         preStart+leftLen)
        curNode.right = self.build(inorder, curInIndex+1, inEnd,        preorder, preStart+1+leftLen, preEnd)
        return curNode

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if len(inorder) == 0:
            return None
        self.inDict = {}
        for index,each in enumerate(inorder):
            self.inDict[each] = index
        self.preIndex = 0
        return self.build(inorder, 0, len(inorder) - 1, preorder)
    def build(self, inorder, inStart, inEnd, preorder):
        # Like problem 106, we use inDict to determine the curInIndx and left/right nodes
        if inStart > inEnd:
            return None
        curVal = preorder[self.preIndex]
        curInIndex = self.inDict[curVal]
        leftLen = curInIndex - inStart
        curNode = TreeNode(curVal)
        self.preIndex += 1
        curNode.left = self.build(inorder,  inStart,      curInIndex-1, preorder)
        curNode.right = self.build(inorder, curInIndex+1, inEnd,        preorder)
        return curNode