[leetcode] 889. Construct Binary Tree from Preorder and Postorder Traversal

Description

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example 1:

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1] Output: [1,2,3,4,5,6,7]

Note:

1 <= pre.length == post.length <= 30pre[] and post[] are both permutations of 1, 2, …, pre.length.It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

分析

题目的意思是：根据前序遍历和后序遍历构造二叉树，根据所学的知识构造的二叉树是不唯一的，因此题目说了至少存在一种答案。我也没做出来，我说一下别人的思路，根据后续遍历找根结点把前序遍历的结果分成左右两个部分就行了。实现的话用递归，注意终止条件是pre数组的元素为空，不是None，今天我才知道[]和None不一样，其他的就是递归构造二叉树了啊。

代码

# 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, pre: List[int], post: List[int]) -> TreeNode: if(not pre): return None root=TreeNode(post.pop()) if(len(pre)==1): return root rightIdx=pre.index(post[-1]) root.right=self.constructFromPrePost(pre[rightIdx:],post) root.left=self.constructFromPrePost(pre[1:rightIdx],post) return root

参考文献

[LeetCode] Python Easy Solution