LeetCode面试题07.重建一棵二叉树【剑指Offer】【中等】【Python】【二叉树】【递归】题目是输入一个某二叉树由于先序遍历和中序遍历，请重建二叉树。假设输入的前序遍历和中序遍历的结果都不包含重复数。例如给定前序遍历preorder=[3,9,20,15,7]inorder遍历inorder=[9,3,15,20,7]返回如下二叉树：3/\920/\157limits:0<=nodes<=numberofnodes<=5000注：本题与主站105题相同。索引是在中序遍历期间确定的。根据索引分为左子树和右子树。如此递归。注意：确保递归前序和中序数一致。时间复杂度：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链接
