桂林新站优化,一键生成vi设计,全能医院网站管理系统,如何做好网站推广工作重建二叉树
题目描述 给定节点数为 n 的二叉树的前序遍历和中序遍历结果#xff0c;请重建出该二叉树并返回它的头结点。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}#xff0c;则重建出如下图所示。 提示: 1.vin.length pre.length 2.pre 和…重建二叉树
题目描述 给定节点数为 n 的二叉树的前序遍历和中序遍历结果请重建出该二叉树并返回它的头结点。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}则重建出如下图所示。 提示: 1.vin.length pre.length 2.pre 和 vin 均无重复元素 3.vin出现的元素均出现在 pre里 4.只需要返回根结点系统会自动输出整颗树做答案对比 数据范围n≤2000节点的值−10000≤val≤10000 要求空间复杂度 O(n)时间复杂度 O(n)
思考了好几天没有想到解题方法以下方案参考了大家的解题思路 采用的方法递归 递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程最重要的就是查看能不能讲原本的问题分解为更小的子问题这是使用递归的关键。 思路二叉树的前序遍历我们可以直到第一个元素是根节点因为序列没有重复的元素我们可以从中序遍历中找到根节点将一个树分为左子树和右子树两个部分。 具体做法
先根据前序遍历第一个点构建根节点然后根据中序遍历找到根节点在数组中的位置再按照字数的节点数将两个遍历的序列分割成子数组将子数组送入函数构建子树直到子树的序列长度为0结束递归。
class TreeNode:def __init__(self, x):self.val xself.left Noneself.right None
#
# 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可
#
#
# param preOrder int整型一维数组
# param vinOrder int整型一维数组
# return TreeNode类
#
class Solution:def reConstructBinaryTree(self , preOrder: List[int], vinOrder: List[int]) - TreeNode:# write code here# 分别获取中序遍历和前序遍历的长度len_pre len(preOrder)len_vin len(vinOrder)# 判断这两个长度都不为0if len_pre 0 or len_vin 0:return None# 构建根节点root TreeNode(preOrder[0])# 从中序遍历中找到根节点所在的位置for i in range(len_vin):if preOrder[0] vinOrder[i]:# 获取左子树的前序遍历left_pre preOrder[:i]# 获取左子树的中序遍历left_vin vinOrder[1:i1]# 构建左子树root.left reConstructBinaryTree(left_pre, left_vin)# 获取右子树的前序遍历right_pre preOrder[i1:]# 获取右子树的中序遍历right_vin vinOrder[i1:]# 构建右子树root.right reConstructBinaryTree(right_pre, right_vin)breakreturn root
