class Solution(object):
    def buildTree(self, preorder, inorder):
        self.pos = {} 
        self.preorder = preorder

        for i, val in enumerate(inorder):
            self.pos[val] = i
        return self.recur(0, 0, len(inorder) - 1)

    def recur(self, pre_left, in_left, in_right):
        #当只有一个节点 in_left == in_right
        #当为空的时候 in_left > in_right   
        if in_left > in_right: # 出口
            return None
        root_val = self.preorder[pre_left]
        root = TreeNode(root_val) 
        k = self.pos[root_val]    
        left_length = k - in_left

        root.left = self.recur(pre_left + 1, in_left, k - 1) 

        root.right = self.recur(pre_left + 1 + left_length, k + 1, in_right) 
        return root