原题链接： https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
根据一棵树的前序遍历与中序遍历构造二叉树。
image.png
解题思路：
- 同题：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
- 根据前序遍历的特性，前序list的首位即为根节点，并在中序list中寻找该节点，左边
[9]即为根节点的左子树，右边[15,20,7]即为根节点的左子树， 因此维护一个词典，存储中序遍历的val->idx。
Python3代码：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def helper(left, right):
if left > right:
return None
# 前序遍历的第一位即root
val = preorder.pop(0)
root = TreeNode(val)
# 构建左子树
root.left = helper(left, idx_map[val]-1)
# 构建右子树
root.right = helper(idx_map[val]+1, right)
return root
idx_map = {val:idx for idx, val in enumerate(inorder)}
return helper(0, len(inorder)-1)
