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

[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 = rightclass 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​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。