根据一棵树的前序遍历与中序遍历构造二叉树。

注意:

你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]

中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

3

/ \

9 20

/ \

15 7

 

1 class Solution: 2     def buildTree(self, preorder, inorder): 3         """ 4         :type preorder: List[int] 5         :type inorder: List[int] 6         :rtype: TreeNode 7         """ 8         def helper(in_left = 0, in_right = len(inorder)): 9             nonlocal pre_idx10             # if there is no elements to construct subtrees11             if in_left == in_right:12                 return None13             14             # pick up pre_idx element as a root15             root_val = preorder[pre_idx]16             root = TreeNode(root_val)17 18             # root splits inorder list19             # into left and right subtrees20             index = idx_map[root_val]21 22             # recursion 23             pre_idx += 124             # build left subtree25             root.left = helper(in_left, index)26             # build right subtree27             root.right = helper(index + 1, in_right)28             return root29         30         # start from first preorder element31         pre_idx = 032         # build a hashmap value -> its index33         idx_map = {val:idx for idx, val in enumerate(inorder)} 34         return helper()