# 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 __init__(self):
        self.hash_table = dict()

    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        n=len(preorder)
        for i in range(0,n):
            self.hash_table[inorder[i]]=i

        root = self.dfs(0,len(preorder)-1,0,len(inorder)-1,preorder,inorder)

        return root

    def dfs(self,pl,pr,il,ir,preorder,inorder):

        if pl > pr:
            return None

        root = TreeNode(preorder[pl])

        k = self.hash_table[root.val]

        left_tree_len = k-1-il+1
        right_tree_len = ir-(k+1)+1

        left_tree = self.dfs(pl+1,pl+left_tree_len,il,k-1,preorder,inorder)
        right_tree = self.dfs(pr+1-right_tree_len,pr,k+1,ir,preorder,inorder)

        root.left = left_tree
        root.right = right_tree

        return root