思路：

递归分析
前序知根值，中序找根位，中序根左右即为左右子树
中序得左右子树节点数，前序根后顺延即得左右子树

详细步骤
1、通过前序遍历序列的第一个点找到根节点的值
2、再根据根节点的值在中序序列中找到根节点的位置
3、中序序列根左边是左子树中序序列，右边是右子树中序序列
4、在中序序列中可以统计左、右子树节点个数分别lenl,lenr
5、在前序序列根右边的lenl个数就是左子树前序序列，左子树后面lenr个数为右子树前序序列
6、从而我们得到左右子树的前序和中序序列，这样就可以递归了

提速

如何快速在中序序列中找到根节点的位置
# 处理：可以用哈希表存储中序序列中每个数的下标是多少
# 这样每次用o(1)时间查找出根节点位置，总共就是o(n)时复

注：python中用字典可代替哈希表

# 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:
        n = len(preorder)
        self.pos = {} # python用字典可实现哈希表功能
        for i in range(n):
            self.pos[inorder[i]] = i # 无重复元素，不考虑冲突
        return self.dfs(preorder, inorder, 0, n - 1, 0, n - 1)

    def dfs(self, preorder, inorder, pl, pr, il, ir):
        if pl > pr: return None # 没有左子树的话
        val = preorder[pl] # 根节点的值
        k = self.pos[val] # 查找根在中序序列中的位置
        len = k - il # 左子树的长度
        root = TreeNode(val)
        root.left = self.dfs(preorder, inorder, pl + 1, pl + len, il, k - 1)
        root.right = self.dfs(preorder, inorder, pl + len + 1, pr, k + 1, ir)

        return root # 最后记得返回根节点


# 思路：
# 1、通过前序遍历序列的第一个点找到根节点的值
# 2、再根据根节点的值在中序序列中找到根节点的位置
# 3、中序序列根左边是左子树中序序列，右边是右子树中序序列
# 4、在中序序列中可以统计左、右子树节点个数分别lenl,lenr
# 5、在前序序列根右边的lenl个数就是左子树前序序列，左子树后面lenr个数为右子树前序序列
# 6、从而我们得到左右子树的前序和中序序列，这样就可以递归了

# 提速
# 如何快速在中序序列中找到根节点的位置
# 处理：可以用哈希表存储中序序列中每个数的下标是多少
# 这样每次用o(1)时间查找出根节点位置，总共就是o(n)时复