README.md

889. 根据前序和后序遍历构造二叉树

English Version

题目描述

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

 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 的排列
• 每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。

解法

Python3

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:
        n = len(preorder)
        if n == 0:
            return None
        root = TreeNode(preorder[0])
        if n == 1:
            return root
        for i in range(n - 1):
            if postorder[i] == preorder[1]:
                root.left = self.constructFromPrePost(
                    preorder[1: 1 + i + 1], postorder[: i + 1])
                root.right = self.constructFromPrePost(
                    preorder[1 + i + 1:], postorder[i + 1: -1])
                return root

Java

...