由遍历序列构造二叉树--王道
2023-06-13 09:13:09 时间
目录
若只给出一棵二叉树的前/中/后/层 序遍历序列的一种,不能唯一确定一棵二叉树
前序遍历 + 中序遍历序列
前序遍历:根结点、前序遍历左子树,前序遍历右子树
中序遍历:中序遍历左子树,根结点,中序遍历右子树
例子:
(图有问题,绿色的点应该是c)
我们分析前序遍历第一个出现的结点一定为根结点,所以A为根结点,而中序遍历左边一定为左子树遍历的序列即BDC,右边右子树为E。
而同样的道理看BDC的话,由前序排列知D为根结点,由中序遍历知左子树为B,右子树为E。
后序+中序遍历序列
后序遍历: 前序遍历左子树 、 前序遍历右子树、根节点
中序遍历:中序遍历左子树,根结点,中序遍历右子树
例子
我们看这个题目后序遍历最右边为根结点,由中序遍历 可分为 左:EAF 右:HCBGI
看左边的序列 EAF ,而在后序遍历那为EFA,可知A为“根结点”,左:E 右:F
看右边的序列HCBGI,前序遍历那为HCIGB,可知B为“根结点”,左:HC 右:GI
最后可知 H在左,C在右,G在左 ,I 在右
层序遍历+中序遍历序列
开始时知道D在层序序列为第一个遍历所以,D为根结点,左子树:EAF,右子树:HCBGI
之后由中序遍历层序遍历知A为左子树的根结点,B为右子树的根结点,然后不难知A的左孩子为 E,右孩子为F。
由层序遍历知,EF后面为CG所以它俩在中间,C 和 G 分别在中间,在看中序遍历序列 C的左边挂H,G的右边挂I
相关文章
- JS数组遍历的几种方法
- c语言list嵌套遍历「建议收藏」
- 如何遍历ArrayList集合,并安全删除其中的元素[通俗易懂]
- 剑指offer No.23 二叉搜索树的后序遍历序列
- Java基础-遍历数组
- vue遍历数组中的数组_vue数组转json
- 软件测试|UI遍历的初步尝试
- 【Windows 逆向】CE 地址遍历工具 ( CE 结构剖析工具 | 遍历查找后坐力数据 | 尝试修改后坐力数据 )
- 算法刷题-二叉树的锯齿形层序遍历、用栈实现队列 栈设计、买卖股票的最佳时机 IV
- leetcode: 二叉树的层序遍历
- LeetCode——遍历序列构造二叉树
- Objective-C遍历数组NSArray的3种方法详解手机开发
- 算法-二叉搜索树的后序遍历序列详解编程语言
- 二叉搜索树的后序遍历序列算法详解编程语言
- 【Linux C 编程实现目录遍历】(linuxc遍历目录)
- js遍历对象的属性的代码
- 判断整数序列是否为二元查找树的后序遍历结果的解决方法
- python二叉树遍历的实现方法
- php无限遍历文件夹示例分享