0889：根据前序和后序遍历构造二叉树（1731 分）

力扣第 98 场周赛第 3 题

题目

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

如果存在多个答案，您可以返回其中 任何 一个。

示例 1：

输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

示例 2:

输入: preorder = [1], postorder = [1]
输出: [1]

提示：

• 1 <= preorder.length <= 30
• 1 <= preorder[i] <= preorder.length
• preorder 中所有值都 不同
• postorder.length == preorder.length
• 1 <= postorder[i] <= postorder.length
• postorder 中所有值都 不同
• 保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历

分析

和 0105 类似的思路。pre[0] 和 pos[-1] 是根节点，pre[1] 有两种情况：

存在左子树，pre[1] 代表左子树

不存在左子树，pre[1] 代表右子树

这里有个巧妙的想法。将右子树所有节点移到左子树，二叉树的前序和后序遍历不变。因此可以令 pre[1] 代表左子树。

在 post 中找到 pre[1] 的位置 i，那么 post[:i+1]、post[i+1:-1] 分别代表左子树、右子树。 对应的 pre[1:i+2]、pre[i+2:] 分别代表左子树、右子树。即可递归。

解答

1
2
3
4
5
6
7

def constructFromPrePost(self, pre: List[int], post: List[int]) -> TreeNode:
	if not pre:
		return None
	if len(pre) == 1:
		return TreeNode(pre[0])
	i = post.index(pre[1])
	return TreeNode(pre[0], self.constructFromPrePost(pre[1:i+2], post[:i+1]), self.constructFromPrePost(pre[i+2:], post[i+1:-1]))

60 ms