返回与给定的前序和后序遍历匹配的任何二叉树。
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
的排列 - 每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。
前序遍历的第一个元素，后续遍历的最后一个元素，是根节点；
从前序看 2 是左树的根节点，我们需要知道左树的长度，我们从后续找到2的位置，4，5，2 是整个左树。
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def constructFromPrePost(self, pre, post):
"""
:type pre: List[int]
:type post: List[int]
:rtype: TreeNode
"""
tree_root = TreeNode(pre[0])
pre = pre[1:]
post = post[:-1]
len_left = 0
for i in post:
if i == pre[0]:
len_left += 1
break
else:
len_left += 1
# print(pre, post)
# print(len_left, pre[:len_left], pre[len_left:])
if len_left >= 1:
tree_root.left = self.constructFromPrePost(
pre[:len_left], post[:len_left])
if len(pre) - len_left >= 1:
tree_root.right = self.constructFromPrePost(
pre[len_left:], post[len_left:])
return tree_root
print(Solution().constructFromPrePost(
pre=[1, 2, 4, 5, 3, 6, 7],
post=[4, 5, 2, 6, 7, 3, 1]))
版权声明：本文为gaorongchao1990626原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。