题解 | #重建二叉树#

前序遍历：根左右
中序遍历：左根右

	class Solution:
    	def reConstructBinaryTree(self , pre: List[int], vin: List[int]) -> TreeNode:
          # write code here
          if not pre or not vin:
              return None
          if len(pre) == 1:
              return TreeNode(pre[0])

          # 前序遍历的第一个元素是根节点
          root_val = pre[0]
          root = TreeNode(root_val)
          # 从中序遍历中找到根节点位置
          root_idx = vin.index(root_val)
          # 根节点左侧元素为左子树，右侧元素为右子树
          left_num = root_idx
          right_num = len(vin) - root_idx - 1
          # 递归构建左右子树
          root.left = self.reConstructBinaryTree(pre[1: left_num + 1], vin[:root_idx])
          root.right = self.reConstructBinaryTree(pre[-right_num:], vin[root_idx+1:])
          return root