105. Construct Binary Tree from

# 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
        """
        def buildTree(i_start,i_end,p_start,p_end):
            if i_start==i_end:return None
            root=TreeNode(preorder[p_start])
            r_idx=inorder[i_start:i_end].index(root.val)
            root.left=buildTree(i_start,i_start+r_idx,p_start+1,p_start+1+r_idx)
            root.right=buildTree(i_start+r_idx+1,i_end,p_start+r_idx+1,p_end)
            return root
        if not preorder or not inorder:return None
        return buildTree(0,len(inorder),0,len(preorder))