#!/usr/bin/env python3

__author__ = 'Wei Mu'

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

#########################
# Other people's answer #
#########################

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if inorder:
            ind = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[ind])
            root.left = self.buildTree(preorder, inorder[0:ind])
            root.right = self.buildTree(preorder, inorder[ind+1:])
            return root


#############
# My answer #
#############

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if preorder == []:
            return None
        
        start = TreeNode(0)
        start.left = self.helper_func(start, preorder, inorder)
        return start.left
    
    
    def helper_func(self, root, preorder, inorder):
        root = TreeNode(preorder[0])
        
        root_ind = inorder.index(preorder[0])
        
        left_inorder = inorder[0:root_ind]
        right_inorder = inorder[root_ind + 1:]
        
        left_preorder = [x for x in preorder if x in left_inorder]
        right_preorder = [x for x in preorder if x in right_inorder]
        
        if len(left_preorder) > 0:
            root.left = self.helper_func(root, left_preorder, left_inorder)
        if len(right_preorder) > 0:
            root.right = self.helper_func(root, right_preorder, right_inorder)
        
        return root
        
        
