难度：★★★☆☆
类型：树
方法：递归
题目
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
返回与给定的前序和后序遍历匹配的任何二叉树。
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 的排列
每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。
解答
这是二叉树的基础题，根据前序和后序遍历重构二叉树。
二叉树的前序遍历为：根节点，左子树，右子树；
二叉树的后续遍历为：左子树，右子树，根节点；
例如由一棵树：
1
/ \
2 3
/ \ / \
4 5 6 7
前序遍历为：1245367
后续遍历为：4526731
树的构建使用递归实现，对于构造函数，对根节点进行处理后，通过递归重复调用实现对每个结点的左子树和右子树的构建。
对于递归函数，包含几个流程：
率先处理终止情况：如果输入的前序遍历和后序遍历的为空，则构造一个空结点，返回None即可；
前序遍历的第一个元素一定是根节点，实例化一棵树，并将根节点的值赋值为该元素；
获取左子树中一共有多少个结点，同时也就知道了右子树种的结点数，方法为，前序遍历的第二个元素是左子树的根节点，在后序遍历中找到这个结点，并获取其下标，由于python中下标是从0而不是1开始的，因此将该下标+1即为左子树种元素的个数；
获取左子树和右子树的前序遍历和后序遍历，有了左子树的元素个数和右子树的元素个数，这是一项很容易的工作；
根据左子树的前序和后序遍历，递归调用本函数实现左子树的构建，同理实现右子树的构建。
class Solution(object):
def constructFromPrePost(self, pre, post):
if not pre:
return None
root = TreeNode(pre[0])
if len(pre) == 1:
return root
left_num = post.index(pre[1]) + 1
left_pre, right_pre = pre[1:left_num+1], pre[left_num+1:]
left_post, right_post = post[:left_num], post[left_num:-1]
root.left = self.constructFromPrePost(left_pre, left_post)
root.right = self.constructFromPrePost(right_pre, right_post)
return root
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
pre = [1, 2, 4, 5, 3, 6, 7]
post = [4, 5, 2, 6, 7, 3, 1]
s = Solution()
r = s.constructFromPrePost(pre, post)
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
