Construct binary tree from preorder and inorder traversal#

 1preorder = [3,9,20,15,7]
 2inorder = [9,3,15,20,7]
 3
 4Return the following binary tree:
 5
 6    3
 7   / \
 8  9  20
 9    /  \
10   15   7

 1class TreeNode(object):
 2    def __init__(self, x):
 3        self.val = x
 4        self.left = None
 5        self.right = None
 6
 7
 8class Solution(object):
 9    def buildTree(self, preorder, inorder):
10        """
11        :type preorder: List[int]
12        :type inorder: List[int]
13        :rtype: TreeNode
14        """
15        if inorder:
16            ind = inorder.index(preorder.pop(0))
17            root = TreeNode(inorder[ind])
18            root.left = self.buildTree(preorder, inorder[0:ind])
19            root.right = self.buildTree(preorder, inorder[ind + 1:])
20            return root