构造二叉树是常见的二叉树考点。比起直接考二叉树的遍历，这种题会难一些。至此（2020-02-08）LeetCode有3个构造二叉树的题目，分别是：105.根据前序和中序遍历序列构造一棵二叉树106.根据中序和后序遍历序列构造一棵二叉树889.根据以前序和后序遍历构建二叉树今天，让我们用一个例程来一举破解它们。105.根据前序和中序遍历序列构造一棵二叉树主题描述根据树的前序遍历和中序遍历构造一棵二叉树。注意：您可以假设树中没有重复元素。例如给定前序遍历preorder=[3,9,20,15,7]inorder遍历inorder=[9,3,15,20,7]返回如下二叉树：3/\920/\157思路我们用题目给出的测试用例来说明：前序遍历是围绕根进行的，所以前序的第一个元素一定是整棵树的根。由于题目说的是没有重复元素，所以我们可以通过val去inorder中找到inorder中根的索引i。又因为中序遍历是左根右的，我们很容易发现i的左子树就是左子树，i的右子树就是右子树。我用红色代表根，蓝色代表左子树，绿色代表右子树。根据此时的信息，我们可以构建的树如下：我们的前序继续向后移动一位，此时我们得到第二个根节点“9”，其实就是左子树的根节点.我们的前序继续向后移动一位，此时我们得到了第二个根节点“20”，它其实就是右子树的根节点。由于右子树的个数大于1，我们无法确定，所以继续执行上面的逻辑。根据此时的信息，我们可以构建的树如下：可以继续执行上面的逻辑。为了简单起见，每次递归时，我都会打开一个新数组。这其实是不必要的。我们可以用四个变量来记录inorder和preorder的起始位置。Code代码支持：Python3Python3Code:classSolution:defbuildTree(self,preorder:List[int],inorder:List[int])->TreeNode:#其实inorder和postorder必须同时为空，所以你不管你是否判断Either是否很好，如果不是预购：returnNoneroot=TreeNode(preorder[0])i=inorder.index(root.val)root.left=self.buildTree(preorder[1:i+1],inorder[:i])root.right=self.buildTree(preorder[i+1:],inorder[i+1:])返回根复杂度分析时间复杂度：由于inorder和preorder的总数会减少1我们每次递归，所以我们需要递归N次，所以时间复杂度是$O(N)$，其中N是节点数。空间复杂度：我们使用递归，也就是使用额外的栈空间来完成。由于堆栈的深度为N，因此总空间复杂度为$O(N)$，其中N是节点数。空间复杂度忽略了创建数组的内存消耗。106.从中序和后序遍历序列构建二叉树。如果你知道上面的话题，那么这个话题对你来说并不难。让我们来看看。题目描述根据树的中序遍历和后序遍历构造一棵二叉树。注意：您可以假设树中没有重复元素。例如给定中序遍历inorder=[9,3,15,20,7]后序遍历postorder=[9,15,7,20,3]返回如下二叉树：3/\920/\157的idea用题目给出的测试用例解释：后序遍历是左右根，所以后序的最后一个元素一定是整棵树的根。由于题目说的是没有重复元素，所以我们可以通过val去inorder中找到inorder中根的索引i。又因为中序遍历是左根右的，我们很容易发现i的左子树就是左子树，i的右子树就是右子树。我用红色代表根，蓝色代表左子树，绿色代表右子树。根据此时的信息，我们可以构造的树如下：因为右子树的个数大于1，所以不能确定，继续执行上面的逻辑。我们的后序继续向前移动一位，此时我们得到了第二个根节点“20”，它其实就是右子树的根节点。根据此时的信息，我们可以构建的树如下：可以继续执行上面的逻辑。为了简单起见，我在递归的时候每次都开辟一个新的数组。这其实是不必要的。我们可以通过四个变量来记录前序和后序的起始位置。Code代码支持：Python3Python3Code:classSolution:defbuildTree(self,inorder:List[int],postorder:List[int])->TreeNode:#其实inorder和postorder必须同时为空，所以你如果不是有序的，你判断Either是否有效并不重要：returnNoneroot=TreeNode(postorder[-1])i=inorder.index(root.val)root.left=self.buildTree(inorder[:i],postorder[:i])root.right=self.buildTree(inorder[i+1:],postorder[i:-1])returnrootcomplexity分析时间复杂度：由于我们的inorder和postorder的总数会每过1减1一次我们递归，所以我们要递归N次，所以时间复杂度是$O(N)$，其中N是节点数。空间复杂度：我们使用递归，也就是使用额外的栈空间来完成。由于堆栈的深度为N，因此总空间复杂度为$O(N)$，其中N是节点数。空间复杂度忽略了创建数组的内存消耗。889.ConstructBinaryTreesFromPreorderandPostorderTraversals题目描述返回匹配给定的前序和后序遍历的任何二叉树。前后遍历中的值是不同的正整数。示例：输入：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<=30pre[]和post[]是1,2,...,pre.length的排列，每个输入保证在至少一个答案。如果有多个答案，可以返回其中一个。题目给出的测试用例解释了思路：前序遍历是围绕根进行的，所以前序的第一个元素一定是整棵树的根，而前序的第二个元素（如果存在的话）一定是左边子树。由于题目说的是没有重复元素，所以我们可以通过val去postorder，找到pre[1]在postorder中的索引i。而且由于后序遍历是左右根，所以我们很容易得到。后序0到i（含）是左子树，前序1到i+1（含）也是左子树。其他部分可以参考上面两个问题。Code代码支持：Python3Python3Code:classSolution:defconstructFromPrePost(self,pre:List[int],post:List[int])->TreeNode:#其实pre和post必须同时为空，所以你可以判断哪个有效ifnotpre:returnNonenode=TreeNode(pre[0])iflen(pre)==1:returnnodei=post.index(pre[1])node.left=self.constructFromPrePost(pre[1:i+2],post[:i+1])node.right=self.constructFromPrePost(pre[i+2:],post[i+1:-1])返回节点复杂度分析时间复杂度：由于每递归一次，我们的后序和预序总数都会减少1，我们需要递归N次，所以时间复杂度是$O(N)$，其中N是节点数。空间复杂度：我们使用递归，也就是使用额外的栈空间来完成。由于堆栈的深度为N，因此总空间复杂度为$O(N)$，其中N是节点数。空间复杂度忽略了创建数组的内存消耗。总结如果仔细比较，你会发现我们的思路和代码几乎是一模一样的。注意每次递归我们两个数组的个数都会减1，所以我们递归的终止条件不难写，也很容易缩小递归问题的规模，即数组总长度减1。以最后一个题目为例：node.left=self.constructFromPrePost(pre[1:i+2],post[:i+1])node.right=self.constructFromPrePost(pre[i+2:],post[i+1:-1])我们发现pre被拆分成了两部分，pre[1:i+2]和pre[i+2:]。显然total少了1，也就是pre的第一个元素。也就是说，你写了一个，另一个可以不假思索地写出来。post也一样，post[:i+1]和post[i+1:-1]，显然总数少了1，也就是post的最后一个元素。这个解题模板够简洁，逻辑清晰，大家可以试试我的模板~关注我欢迎关注我的公众号《脑洞前端》，获取更多更新鲜的LeetCode题解
