105。根据前序和中序遍历序列构造二叉树题目来源：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal题目根据前序遍历和构造二叉树树的中序遍历。注意：您可以假设树中没有重复元素。例如给定前序遍历preorder=[3,9,20,15,7]inorder遍历inorder=[9,3,15,20,7]返回如下二叉树：3/\920/\157解题意：这里递归，先说一下前序遍历和中序遍历的概念。前序遍历：先访问根节点，再遍历左子树，最后遍历右子树。中序遍历：先遍历左子树，再访问根节点，最后遍历右子树。也就是说两者的遍历顺序是：前序遍历：根节点->左子树->右子树中序遍历：左子树->根节点->右子树根据上面可以看出order，前序遍历时，第一个为根节点；而在中序遍历中，根节点的左边是左子树，右边是右子树。根据这个特点，我们来看一个例子。前序遍历preorder=[3,9,20,15,7]inorder遍历inorder=[9,3,15,20,7]本例中先序遍历preorder的第一个元素3为根节点，看中序遍历，中序3的左[9]为左子树，右[15,20,7]为右子树。按照这个思路，可以构造出一棵完全二叉树。下面是具体思路：先找到根节点（依据：前序遍历顺序，先遍历根节点）构建根节点的左子树（依据：中序遍历，左边的根节点是左子树）构建根节点的右子树（依据：中序遍历，根节点右边的是右子树）。在题目中，有一个提示：【假设树中没有重复的元素】。根据这个提示，我们在前序遍历中找到的根节点元素可以根据元素值定位到它在中序遍历中的位置。具体代码实现如下。代码实现#定义二叉树节点。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案：defbuildTree(self,preorder:List[int],inorder:List[int])->TreeNode:defbuild_tree(pre_left,pre_right,in_left,in_right):"""构建二叉树Args:pre_left:前序遍历左边界pre_right:前序遍历右boundaryin_left:后序遍历左边界in_right:后序遍历右边界"""#终止条件ifin_left>in_right:returnNone#按照前序遍历的顺序，第一个元素为根节点pre_root=pre_left#构建根节点root=TreeNode(preorder[pre_root])#如题所示，假设树中没有重复元素#然后根据根节点的值，定位到in_root=inorder.index(root.val)#按照中序遍历的访问顺序，根节点的左边就是左subtree,右边是右子树#这里先得到左子树节点数size_left_subtree=in_root-in_left#构造左子树#这里对根节点（不包括根节点）左边的节点进行中序遍历，其实相当于左边界的下一位+size_left_subtree节点的前序遍历#即，从in_left的前一位到inroot的部分节点，等于从pre_left的下一位开始的size_left_subtree元素root.left=build_tree(pre_left+1,pre_left+size_left_subtree,in_left,in_root-1)#构建右子树#at这次中序遍历根节点右边的部分节点（不包括根节点），对应前序从左边界+1+sub_left_subtree遍历到它的右边界root.right=build_tree(pre_left+1+size_left_subtree,pre_right,in_root+1,in_right)returnrootsize=len(inorder)returnbuild_tree(0,size-1,0,size-1)执行结果总结首先，按照前序遍历访问的顺序，先查找二进制文件的根节点y树，构建根节点。因为题目描述可以假设没有重复的元素，那么可以根据上面找到根节点的值，在inorder遍历inorder中找到它的位置。根据中序遍历的访问顺序，可以确定当前找到的根节点左边的部分是左子树，右边的部分是右子树。然后根据上面分析的情况，递归构造左子树和右子树。欢迎关注微信公众号《书所集录》
