'''
Description: 
Autor: Au3C2
Date: 2021-03-24 16:24:40
LastEditors: Au3C2
LastEditTime: 2021-03-24 16:25:25
'''
class Solution(object):
    def constructFromPrePost(self, pre, post):
        def dfs(pre,post):
            if not pre:
                return None
            # 数组长度为1时，直接返回即可
            if len(pre)==1:
                return TreeNode(pre[0])
            # 根据前序数组的第一个元素，创建根节点     
            root = TreeNode(pre[0])
            # 根据前序数组第二个元素，确定后序数组左子树范围
            left_count = post.index(pre[1])+1
            # 递归执行前序数组左边、后序数组左边
            root.left = dfs(pre[1:left_count+1],post[:left_count])
            # 递归执行前序数组右边、后序数组右边
            root.right = dfs(pre[left_count+1:],post[left_count:-1])
            # 返回根节点
            return root
        return dfs(pre,post)

# 树，中等。构造树三题齐活。前后序难一些
# https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/