# 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 or len(preorder)==0:

            return

        pos = inorder.index(preorder[0])

        root = TreeNode(preorder[0])

        root.left = self.buildTree(preorder[1:pos+1], inorder[:pos])

        root.right = self.buildTree(preorder[pos+1:],inorder[pos+1:])

        return root

class Solution(object):

    def buildTree(self, preorder, inorder):

        """

        :type preorder: List[int]

        :type inorder: List[int]

        :rtype: TreeNode

        """

        if not inorder or not preorder:

            return None

        map = {val:idx for idx, val in enumerate(inorder)}

        pos = map[preorder[0]]

        root = TreeNode(preorder[0])

        root.left = self.buildTree(preorder[1:pos+1], inorder[:pos])

        root.right = self.buildTree(preorder[pos+1:],inorder[pos+1:])

        return root