题解 | #重建二叉树#

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param preOrder int整型一维数组
# @param vinOrder int整型一维数组
# @return TreeNode类
#
class Solution:
    def reConstructBinaryTree(self, pre: List[int], vin: List[int]) -> TreeNode:
        # 如果前序遍历列表为空，则返回None
        if not pre:
            return None

        # 找到前序遍历中根节点在中序遍历中的索引
        index = vin.index(pre[0])

        # 创建根节点
        root = TreeNode(pre[0])

        # 递归构建左子树
        # 注意：pre[1:index+1]表示左子树的前序遍历，vin[:index]表示左子树的中序遍历
        root.left = self.reConstructBinaryTree(pre[1 : index + 1], vin[:index])

        # 递归构建右子树
        # 注意：pre[index+1:]表示右子树的前序遍历，vin[index+1:]表示右子树的中序遍历
        root.right = self.reConstructBinaryTree(pre[index + 1 :], vin[index + 1 :])

        # 返回根节点
        return root