首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

我的代码中出现了一个错误。问题:从预序和中序遍历构造二叉树

问题:从预序和中序遍历构造二叉树

回答: 从预序和中序遍历构造二叉树是一个经典的算法问题。首先,我们需要了解预序遍历和中序遍历的概念。

预序遍历(Preorder Traversal)是指先访问根节点,然后按照先左后右的顺序遍历左子树和右子树。

中序遍历(Inorder Traversal)是指先按照左子树、根节点、右子树的顺序遍历左子树,然后访问根节点,最后按照左子树、根节点、右子树的顺序遍历右子树。

根据题目给出的预序遍历和中序遍历序列,我们可以通过递归的方式构造二叉树。

具体步骤如下:

  1. 首先,我们需要找到根节点。根据预序遍历的定义,预序遍历序列的第一个元素即为根节点。
  2. 然后,我们在中序遍历序列中找到根节点的位置。根据中序遍历的定义,根节点的左边即为左子树的中序遍历序列,根节点的右边即为右子树的中序遍历序列。
  3. 接下来,我们可以根据中序遍历序列中根节点的位置,将预序遍历序列分为左子树的预序遍历序列和右子树的预序遍历序列。
  4. 然后,我们可以递归地构造左子树和右子树。递归的终止条件是当左子树或右子树的遍历序列为空时,返回空节点。
  5. 最后,我们将根节点与左子树和右子树连接起来,构成完整的二叉树。

以下是一个示例代码,用于从预序和中序遍历构造二叉树:

代码语言:txt
复制
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def buildTree(preorder, inorder):
    if not preorder or not inorder:
        return None
    
    root_val = preorder[0]
    root = TreeNode(root_val)
    
    root_index = inorder.index(root_val)
    
    left_inorder = inorder[:root_index]
    right_inorder = inorder[root_index+1:]
    
    left_preorder = preorder[1:1+len(left_inorder)]
    right_preorder = preorder[1+len(left_inorder):]
    
    root.left = buildTree(left_preorder, left_inorder)
    root.right = buildTree(right_preorder, right_inorder)
    
    return root

# 示例调用
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
root = buildTree(preorder, inorder)

在腾讯云的产品中,与二叉树相关的服务包括云数据库 CDB、云服务器 CVM、云函数 SCF 等。具体的产品介绍和链接地址可以参考腾讯云官方文档。

注意:以上代码仅为示例,实际应用中可能需要根据具体情况进行调整和优化。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

☆打卡算法☆LeetCode 105、从前序与遍历序列构造二叉树 算法解析

一、题目 1、算法题目 “给定两个整数数组preino,其中pre是二叉树遍历,ino是二叉树遍历构造二叉树返回其根节点。”...,这道题是由两个整数数组,一个遍历一个遍历构造二叉树返回根节点。...前序遍历遍历长度是相同,可以将遍历结果对应到前序遍历结果 根据前序遍历遍历结果,以及右子树前序遍历遍历结果,我们就可以递归地构造出左子树右子树 将这两颗字数连接到根节点左右位置...先遍历 左边界+1 开始 size_left_subtree」个元素就对应遍历 左边界 开始到 根节点定位-1」元素 root.left = myBuildTree...,并连接到根节点 // 先遍历 左边界+1+左子树节点数目 开始到 右边界」元素就对应遍历 根节点定位+1 到 右边界」元素 root.right

21830

二叉树各种遍历真的很难?大sai带你拿捏!

前言 大家好,是bigsai,好久不见,甚是想念! 今天带大家征服二叉树后序遍历,包含递归非递归方式,学到就是赚到!...二叉树遍历出现频率还是蛮高,如果是二叉排序树相关问题还是蛮多,你要知道二叉排序树遍历一个有序序列,如果求二叉排序树topk问题,非递归中那效率是非常高。...前序、确定二叉树后序、确定一个二叉树原理一致。 前序确定一棵二叉树 根据一棵树前序遍历遍历构造二叉树。当然也是力扣105原题。 注意:你可以假设树没有重复元素。...分析: 给定一个前序序列一个序列,且里面没有重复元素,如何构造一棵二叉树呢?我们可以先单独观察两个序列特征: 前序遍历遍历规则为(根,[左侧区域],[右侧区域])。.../ \ 15 7 分析: 有上面的分析,那么通过一个后序遍历遍历构造一棵二叉树,其实原理前面的也是一样

60630

二叉树:总结篇!(需要掌握二叉树技能都在这里

给「代码随想录」一个星标吧! ❝二叉树大总结!...类似层遍历 求二叉搜索树属性 二叉搜索树搜索 递归:二叉搜索树递归是有方向 迭代:因为有方向,所以迭代法很简单 是不是二叉搜索树 递归:,相当于变成了判断一个序列是不是递增 迭代:模拟...递归:,双指针操作累加 迭代:模拟,逻辑相同 二叉树公共祖先问题 二叉树公共祖先问题 递归:后序,回溯,找到左子树出现目标值,右子树节点目标值节点。...迭代:不适合模拟回溯 二叉搜索树公共祖先问题 递归:顺序无所谓,如果节点数值在目标区间就是最近公共祖先 迭代:按序遍历 二叉搜索树修改与构造 二叉搜索树插入操作 递归:顺序无所谓,通过递归函数返回值添加节点...求二叉搜索树属性,一定是,要不白瞎了有序性。 注意在普通二叉树属性是一般为后序,例如单纯求深度就用前序, 二叉树:找所有路径也用了前序,这是为了方便让父节点指向子节点。

79841

为实习准备数据结构(4)-- 二叉树

这样以来,我们就知道左子树前序遍历遍历结果,以及右子树前序遍历遍历结果,我们就可以递归地对构造出左子树右子树,再将这两颗子树接到根节点左右位置。...对于哈希映射中每个键值对,键表示一个元素(节点值),值表示其在遍历出现位置。在构造二叉树过程之前,我们可以对遍历列表进行一遍扫描,就可以构造出这个哈希映射。...在此后构造二叉树过程,我们就只需要 O(1) 时间对根节点进行定位。 下面的代码给出了详细注释。...---- 已知后序、遍历结果,还原二叉树 这个LeetCode上没找到,模仿着写一个。 //一、二步同上 //其实第三步原理是一样,不过我们脑子习惯了从前到后,所以,让帮你们转个弯。...这样以来,我们就知道左子树后序遍历遍历结果,以及右子树后序遍历遍历结果,我们就可以递归地对构造出左子树右子树,再将这两颗子树接到根节点左右位置。

36110

【甘泉算法】一文搞定还原二叉树问题

105题 从前序与遍历序列构造二叉树 做出来,讨论问题是一样。...889题 根据前序后序遍历构造二叉树 做出来,讨论问题是一样。...四、根据后序遍历构造二叉树 我们已经一起解决根据前序,前序后序遍历结果序列来还原二叉树,现在我们一起看下这个题型最后一道题:根据后序遍历构造二叉树。...本小节讨论问题leetcode 106题一样:从中与后序遍历序列构造二叉树 ,我们目前还是以前面的二叉树为例,这里列出遍历后序遍历序列如下: 根据上面的遍历后序遍历,该如何正确还原成一棵二叉树呢...其实需要用到遍历后序遍历两个基本特性,想,说到这, 读者肯定知道它们特性,因为前面两小节都已经阐述过了,没错,就是下面两个基本点: 在后序遍历结果,最后一个位置元素是二叉树根节点;

28220

二叉树链式结构实现二叉树遍历以及判断完全二叉树

leftheight + 1 : rightheight+1; } 二叉树遍历 前序、以及后序遍历 学习二叉树结构,最简单方式就是遍历。...所谓二叉树遍历(Traversal)是按照某种特定规则,依次对二叉树节点进行相应操作,并且每个节点只操作一次。访问结点所做操作依赖于具体应用问题。...遍历二叉树上最重要运算之一,也是二叉树上进行其它运算基础 按照规则,二叉树遍历有:前序//后序递归结构遍历: 前序遍历(Preorder Traversal 亦称先遍历)——访问根结点操作发生在遍历其左右子树之前...层遍历:除了先遍历遍历、后序遍历外,还可以对二叉树进行层遍历。...设二叉树根节点所在层数为1,层遍历就是所在二叉树根节点出发,首先访问第一层树根节点,然后从左到右访问第2层上点,接着是第三层节点,以此类推,自上而下,自左至右逐层访问树结点过程就是层遍历

7010

树——构造遍历二叉树

构造二叉树遍历二叉树,先+构造二叉树后序遍历+后序构造二叉树遍历。...构造二叉树 根据先遍历结果还原二叉树基础理论比较好理解,多做几道这些类似的题,也能孰能生巧。...关键之处,还是在于代码实现。 这是一道OJ题,请移步HDU1710 因为还原二叉树一个递归问题,将复杂地问题简化为一个个小问题,所以就拿三个结点二叉树举栗。...先:ABC; :BAC; 我们都知道先遍历是根左右,而遍历是左根右,我们可以通过先找到根节点,根据根节点位置,就可以找到根节点左子树(左孩子),右子树(右孩子);根据这个规则就可以还原一颗二叉树...+构造二叉树类似,关键之处在于,找到每个二叉结点根,左孩子,右孩子位置,然后递归就可以

55910

二叉树构建,先,后序遍历(以及非递归实现),广度优先遍历

相关问题在百行代码内就可解决,特别适合手写代码,因此我们要充分做好准备,迎接面试时关于二叉树相关问题,尤其是手写代码。 1....image.png 2.二叉树构建 二叉树前序、后序序列任何一个都不能唯一确定一棵二叉树所知道二叉树构建主要有两大种方法。...网上有很多blog资料都没有将上面的方法列举出来,有个文档资料里说根据扩充二叉树任意一个遍历序列就能唯一确定这棵二叉树。这个说法是错误,这份文档见here。...举一个反例即可证明根据扩充二叉树遍历序列是不能唯一确定二叉树结构,以文档描述为例: image.png 上图中扩展二叉树遍历序列为:#B#D#A#C#,那么也可以对应为下面的扩展二叉树...: image.png 2.1前序+序列构建二叉树(递归实现) 构建过程: (1)前序遍历序列一个数字为根节点,构造根节点; (2)找到根节点在遍历序列位置,根节点左右两边分别为左子树有子树

17.9K56

算法:分治

给定两个整数数组 inorder postorder ,其中 inorder 是二叉树遍历, postorder 是同一棵树后序遍历,请你构造并返回这颗 二叉树 。...基于遍历左子树,能够后续遍历中找到左子树后续遍历;基于遍历右子树,能够后续遍历中找到右子树后续遍历问题分解成了两个小问题,方法一样,采用分治递归思想解决,这里有个小技巧就是使用哈希表存储元素映射位置...给定两个整数数组 preorder inorder ,其中 preorder 是二叉树遍历, inorder 是同一棵树遍历,请构造二叉树并返回其根节点。...inorder 均 无重复 元素 inorder 均出现在 preorder preorder 保证 为二叉树前序遍历序列 inorder 保证 为二叉树遍历序列 解题思路: 与之前遍历后续遍历一样...,并连接到根节点 // 先遍历 左边界+1+左子树节点数目 开始到 右边界」元素就对应遍历 根节点定位+1 到 右边界」元素 root->right

1K30

通过前序+后序+来构建二叉树

在这里插入图片描述 前序 + 题意:给你一个前序遍历遍历,你要构造一个二叉树。...我们能找到根节点,就能找到左子树右子树集合,那么这个二叉树是不是就已经有一个大致样子。 接下来要做,就是使用递归去构建出左子树右子树。 示例过程: ? 1 ? 2 ?...我们会理解了前序遍历构造二叉树,那么后序构造二叉树就不是难事。...二叉树问题绝大部分都是三种遍历有关,思考问题时候,可以三种遍历特点入手。...其他二叉树相关 1、详解算法之重建二叉树 2、二叉树后序遍历(非递归版) 3、二叉树遍历(非递归版) 4、二叉树遍历(非递归版) 5、从上往下打印二叉树 6、二叉搜索树后序遍历序列 7、

2.3K30

Leetcode No.105 从前序与遍历序列构造二叉树

一、题目描述 根据一棵树前序遍历遍历构造二叉树。 注意: 你可以假设树没有重复元素。...这样以来,我们就知道左子树前序遍历遍历结果,以及右子树前序遍历遍历结果,我们就可以递归地对构造出左子树右子树,再将这两颗子树接到根节点左右位置。...对于哈希映射中每个键值对,键表示一个元素(节点值),值表示其在遍历出现位置。在构造二叉树过程之前,我们可以对遍历列表进行一遍扫描,就可以构造出这个哈希映射。...在此后构造二叉树过程,我们就只需要 O(1)时间对根节点进行定位。...,并连接到根节点 // 先遍历 左边界+1+左子树节点数目 开始到 右边界」元素就对应遍历 根节点定位+1 到 右边界」元素 root->right

19010

二叉树

这是构造函数,这么说吧C语言中结构体是C++祖先,所以C++结构体也可以有构造函数。 构造函数也可以不写,但是new一个节点时候就比较麻烦。...我们介绍二叉树另一种遍历方式(图论中广度优先搜索在二叉树应用)即:层遍历。...我们把翻转二叉树这么一道简单又经典问题,充分剖析一波,相信就算做过这道题目的同学,看完本篇之后依然有所收获!...「文中指的是递归遍历是不行,因为使用递归遍历,某些节点左右孩子会翻转两次。」...总结 「本周我们都是讲解了二叉树理论基础到遍历方式,递归到迭代,深度遍历到广度遍历,最后再用了一个翻转二叉树题目把我们之前讲过遍历方式都串起来。」 下周依然是二叉树,大家加油!

43020

☆打卡算法☆LeetCode 106、从中与后序遍历序列构造二叉树 算法解析

一、题目 1、算法题目 “给定两个整数数组inopos,其中ino是二叉树遍历,pos是二叉树后序遍历,请你构造并返回这颗二叉树。”...从中与后序遍历序列构造二叉树 - 力扣(LeetCode) (leetcode-cn.com) 2、题目描述 给定两个整数数组 inorder postorder ,其中 inorder 是二叉树遍历...: 遍历顺序是先遍历左子树,再遍历根节点,最后遍历右子树 后序遍历顺序是先遍历左子树,再遍历右子树,最后遍历根节点 根据遍历后序遍历性质,我们可以知道后序遍历数组最后一个元素就是根节点...根据这个性质,我们可以使用根节点信息在遍历数组中找到根节点所在下标。 然后根据其在遍历数组分成左右两部分,就是左右子树,然后同样方法递归递归构造下去。...在递归过程,利用哈希表(1)时间复杂度查询当前根节点在遍历下标。 根绝后序遍历性质,递归创建右子树左子树,创建左右子树依赖关系,再存储右子树节点,最后存储根节点。

17210

二叉树篇二刷总结

如果上述几个问题你都能够全部想明白并且能够通过代码方式实现, 那么二叉树章节基本是没有什么问题了。...题型题解 二叉树遍历二叉树遍历篇已全部ac, 相关题目在卡哥代码随想录》中都有, 个人建议每个题目都用递归迭代都做一边。...二叉树修改与构造最简单来实现 就是 二叉树反转(虽然最简单但是也难倒了大佬Max Howell)。 最简单方式就是通过递归前序遍历, 然后swap两个子节点。...接下来就是通过前序后序结果来构造二叉树搜索树 106.从中与后序遍历序列构造二叉树 给定两个整数数组 inorder postorder ,其中 inorder 是二叉树遍历...rightInorderEnd, postorder, rightPostorderStart, rightPostorderEnd); return root; } } 105 从前序遍历序列构造二叉树

8210

重建二叉树(Java)

大家好,又见面是你们朋友全栈君。 题目: 输入某二叉树前序遍历遍历结果,请重建出该二叉树。假设输入前序遍历遍历结果中都不包含重复数字。...解题思路: 题目中给了我们先遍历遍历;在二叉树前序遍历,第一个数字总是树根结点值。...题目给出前序遍历序列一个数字1就是根结点值。扫描遍历序列,就能确定根结点位置。...重建二叉树可以有前序推导出来,也可以由中后序推导出来。这里实现由中后序重建二叉树。...,只有掌握二叉树三种遍历,才可以推导出二叉树结构; 这道题它经典之处在于递归,在每次递归时它经典是把一颗完整二叉树,分成了左子树、根、右子树,再在每个左右子树再分,即把大问题转化为局部小问题

24910

【算法提高班】构造二叉树系列

从前序与遍历序列构造二叉树[1] 106. 从中与后序遍历序列构造二叉树[2] 889. 根据前序后序遍历构造二叉树[3] 今天就让我们用一个套路一举攻破他们。 105....从前序与遍历序列构造二叉树 题目描述 根据一棵树前序遍历遍历构造二叉树。 注意: 你可以假设树没有重复元素。...而由于遍历是左根右,我们容易找到 i 左边都是左子树,i 右边都是右子树。 使用红色表示根,蓝色表示左子树,绿色表示右子树。 ? 根据此时信息,我们能构造树是这样: ?...从中与后序遍历序列构造二叉树 如果你会了上面的题目,那么这个题目对你来说也不是难事,我们来看下。 题目描述 根据一棵树遍历与后序遍历构造二叉树。 注意: 你可以假设树没有重复元素。...根据前序后序遍历构造二叉树 题目描述 返回与给定前序后序遍历匹配任何二叉树。 pre post 遍历值是不同正整数。

47210

判断一棵满二叉树是否为二叉搜索树

刚开始写出了这样代码: def judgeBST(self, root): if not root: return True if root.left...分析原因发现,上述代码只能判断每棵子树满足 BST 条件,但是全局 BST 可能就不满足(11 > 10)。...具体错误原因可以参考下面这篇博客,写得很清楚: 判断一棵树是否是二叉搜索树 实际上,我们可以利用 BST 性质:遍历是递增 进行判断。...使用遍历方法实现: 对树进行遍历,将结果保存在 temp 数组; 检测 temp 数组是否为升序排列,如果是,则为 BST,反之则不是。...此方法还可以进一步优化,不用 temp 数组,避免使用额外内存开销。在遍历时使用一个全局变量 pre 保存前驱节点,如果当前节点值小于前驱节点值 pre.val,则该树不是 BST。

1.2K10

二叉树入门就是这么简单!

,也感谢帮助过一个人。...例如 B C 互为兄弟 堂兄弟:双亲互为兄弟结点结点,例如 D E 互为堂兄弟 祖先结点:根结点到达一个结点路径上所有结点,A B D 结点均为 H 结点祖先结点 子孙结点:以某个结点为根子树任意一个结点都称为该结点子孙结点...2,并且最下面一层结点都集中在该层最左边连续位置上,此树可以成为完全二叉树 看着树示意图,心中默默按照满二叉树结构逐层顺序编号,如果编号出现空挡,就说明不是完全二叉树 ?...遍历,就是把每个点都看成头结点,然后每次都执行遍历,也就是(左 - 根 - 右),等左边空了,就返回访问当前结点父节点,也就是,记录后,再访问右 例如:根结点 A 出发,先访问左孩子 B...,确实没有递归方式容易理解,学习这部分时可以对照一个简单图,来思考,可以帮助你更好认识代码,可以参考上面举例图 (二) 广度优先遍历 广度优先遍历,又叫做宽度优先遍历,或者层遍历,思想就是,根节点开始访问

70420
领券