题目描述

返回与给定的前序和后序遍历匹配的任何二叉树。

pre 和 post 遍历中的值是不同的正整数。

示例：

输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

提示：

1 <= pre.length == post.length <= 30
pre[] 和 post[] 都是 1, 2, ..., pre.length 的排列
每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。

我的解法——递归（AC）

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def myconstructFromPrePost(self, pre, post, l1, r1, l2, r2, dic):
        now = TreeNode(pre[l1])
        if(l1 != r1):
            next_head_pre_index = l1 + 1
            next_head_post_index = dic[pre[l1 + 1]]
            left_count = next_head_post_index - l2 + 1
            right_count = r2 - l2 - left_count
            if(left_count):
                now.left = self.myconstructFromPrePost(pre, post, l1 + 1, l1 + left_count, l2, r2 - right_count - 1, dic)
            if(right_count):
                now.right = self.myconstructFromPrePost(pre, post, l1 + left_count + 1, r1, r2 - right_count, r2 - 1, dic)
        return now
        
    def constructFromPrePost(self, pre, post):
        """
        :type pre: List[int]
        :type post: List[int]
        :rtype: TreeNode
        """
        if(not len(pre) or not len(post)):
            return None
        
        dic = {}
        for i in range(len(post)):
            dic[post[i]] = i

        return self.myconstructFromPrePost(pre, post, 0, len(pre) - 1, 0, len(pre) - 1, dic)