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,
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 <= 30
- pre[] 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