从前序与中序遍历序列构造二叉树

该题解使用递归的方式，根据前序遍历和中序遍历的特点构建二叉树。首先，前序遍历的第一个元素一定是根节点。然后，在中序遍历中找到根节点的位置，根据根节点将中序遍历序列分为左右两部分，分别对应根节点的左右子树。接着，递归地对左右子树进行同样的处理，直到所有节点都被处理完。

时间复杂度: O(n^2)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def build(pstart, pend, istart, iend):
            if pstart > pend:
                return
            
            # 前序遍历的第一个元素为根节点
            root_val = preorder[pstart]
            
            # 在中序遍历中查找根节点的位置
            index = istart
            for i in range(istart, iend+1):
                if inorder[i] == root_val:
                    index = i
                    break
            
            # 计算左子树的节点数
            left_length = index - istart
            
            # 构建根节点
            root = TreeNode(root_val)
            
            # 递归构建左子树
            root.left = build(pstart+1, pstart+left_length, istart, istart+left_length)
            
            # 递归构建右子树
            root.right = build(pstart+left_length+1, pend, istart+left_length+1, iend)
            
            return root
        
        return build(0, len(preorder)-1, 0, len(inorder)-1)