LeetCode0106.从中序遍历和后序遍历构造二叉树【中序】【Python】【二叉树】【递归】ProblemLeetCodeGiveninorder和树的后序遍历，构建二叉树。注意：你可以假设树中不存在重复项。例如，giveninorder=[9,3,15,20,7]postorder=[9,15,7,20,3]返回如下二叉树：3/\920/\157问题是根据一棵树的中序遍历和后序遍历构造一棵二叉树。注意：您可以假设树中没有重复元素。例如给定中序遍历inorder=[9,3,15,20,7]后序遍历postorder=[9,15,7,20,3]返回如下二叉树：3/\920/\157思路递归中序遍历：左根右后序遍历：左右根所以，每次后序遍历最后的值都取代表根，然后在in-中确定索引顺序遍历。根据索引分为左子树和右子树。如此递归。注意：保证递归的中序和后序的个数相同。时间复杂度：O(n)，其中n是节点数。空间复杂度：O(n)，其中n是节点数。Python3Definition#定义一个二叉树节点。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案：defbuildTree(self,inorder:List[int],后序:List[int])->TreeNode:如果不是后序:returnNoneroot=TreeNode(postorder[-1].#left:inorder[0]~inorder[i-1],postorder[0]~postorder[i-1]root.left=self.buildTree(inorder[:i],postorder[:i])#right:inorder[i+1]~inorder[-1],postorder[i]~postorder[-2]root.right=self.buildTree(inorder[i+1:],postorder[i:-1])返回root异常GitHub链接
