题目链接

思路：

转换为子问题，使用递归。
前序确定当前子树的根节点，中序则从根节点一分为二，根节点左边为左子树，根节点右边为右子树。问题来了：前序怎么一分为二？
1s…
2s…
3s…
中左右，左中右，这个左的个数是一样的。所以可以根据左中右，算出左的长度。那前序就可以根据这个长度一分为二。然后转换为左右子树子问题

python"># class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
def constructTree(preOrder,vinOrder):# 递归退出条件if len(preOrder) == 0:return None# 根节点root_val = preOrder[0]root = TreeNode(root_val)index = vinOrder.index(root_val)# 左子树leftnode = constructTree(preOrder[1:index+1], vinOrder[:index])# 柚子树rightnode = constructTree(preOrder[index+1:],vinOrder[index+1:])root.left = leftnoderoot.right = rightnodereturn rootclass Solution:def reConstructBinaryTree(self , preOrder: List[int], vinOrder: List[int]) -> TreeNode:# write code here# 根据前序遍历确定中间节点，根据中序遍历，分左右子树return constructTree(preOrder,vinOrder)

还债