'''
Description: 
Autor: Au3C2
Date: 2021-03-24 16:05:00
LastEditors: Au3C2
LastEditTime: 2021-03-24 16:05:14
'''
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if not (inorder and postorder):
            return None
        # 根据前序数组的最后个元素，就可以确定根节点	
        root = TreeNode(postorder[-1])
        # 用postorder[-1]去中序数组中查找对应的元素
        mid_idx = inorder.index(postorder[-1])
        # 递归的处理中序数组的左边部分和后序数组的左边部分
        # 递归处理中序数组右边部分和后序数组右边部分
        root.left = self.buildTree(inorder[:mid_idx],postorder[:mid_idx])
        root.right = self.buildTree(inorder[mid_idx+1:],postorder[mid_idx:len(postorder)-1])
        return root
# 树，中等
# https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/