LeetCode0105.从前序和中序遍历构造二叉树[中][Python][二叉树][递归]ProblemLeetCodeGiven对一棵树进行前序和中序遍历，构建二叉树。注意：你可以假设树中不存在重复项。例如，给定preorder=[3,9,20,15,7]inorder=[9,3,15,20,7]返回如下二叉树：3/\920/\157问题是根据一棵树的前序遍历和中序遍历构造一棵二叉树。注意：您可以假设树中没有重复元素。例如给定前序遍历preorder=[3,9,20,15,7]inorder遍历inorder=[9,3,15,20,7]返回如下二叉树：3/\920/\157思路递归前序遍历：根，左，中序遍历：左根，右所以，每次先序遍历的值取代表根，然后在中序遍历中确定索引.根据索引分为左子树和右子树。如此递归。注意：确保递归前序和中序数一致。时间复杂度：O(n)，其中n是节点数。空间复杂度：O(n)，其中n是节点数。Python3代码#定义一个二叉树节点。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案：defbuildTree(self,preorder:List[int],inorder:List[int])->TreeNode:ifnotpreorder:returnNoneroot=TreeNode(preorder[0])#根据在中序遍历中的搜索i=inorder.index(root.val)#左：preorder[1]~preorder[i],inorder[0]~inorder[i-1]root.left=self.buildTree(preorder[1:i+1],inorder[:i])#右：preorder[i+1]~preorder[-1],inorder[i+1]~inorder[-1]root.right=self.buildTree(preorder[i+1:],inorder[i+1:])返回根代码地址GitHub链接
