算法1

(递归) $O(n)$

# 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 dfs(pl, pr, il, ir):
            """
            pl：前序遍历区间的左端点
            pr：前序遍历区间的右端点
            il：中序遍历区间的左端点
            ir：中序遍历区间的右端点
            """
            if pl > pr:    # 前序遍历区间的左端点大于右端点，说明前序遍历区间为空，此时返回None
                return None
            val = preorder[pl]  # 前序遍历区间的第一个值就是根节点的值
            k = dic[val]  # 找到根节点在中序遍历的索引
            root = TreeNode(val) # 创建根节点
            root.left = dfs(pl+1, pl+k-il,  il, k-1) # 递归左子树
            root.right = dfs(pl+k-il+1, pr, k+1, ir) # 递归右子树
            return root # 返回根节点


        dic = {} # 记录中序遍历每个值对应的索引，方便通过前序遍历的值查找该值在中序遍历的位置，只要用来确定根节点在中序遍历的位置，从而区分左右子树
        for i, num in enumerate(inorder):
            dic[num] = i

        return dfs(0, len(preorder) - 1, 0, len(inorder) - 1)