由遍历序列构造二叉树--王道

简介: 前序遍历 + 中序遍历序列后序+中序遍历序列层序遍历+中序遍历序列

目录

前序遍历 + 中序遍历序列

后序+中序遍历序列

层序遍历+中序遍历序列


若只给出一棵二叉树的前/中/后/层 序遍历序列的一种,不能唯一确定一棵二叉树

image.png

前序遍历 + 中序遍历序列

前序遍历:根结点、前序遍历左子树,前序遍历右子树

中序遍历:中序遍历左子树,根结点,中序遍历右子树

例子

image.png

(图有问题,绿色的点应该是c)


我们分析前序遍历第一个出现的结点一定为根结点,所以A为根结点,而中序遍历左边一定为左子树遍历的序列即BDC,右边右子树为E。


而同样的道理看BDC的话,由前序排列知D为根结点,由中序遍历知左子树为B,右子树为E。


后序+中序遍历序列

后序遍历: 前序遍历左子树 、 前序遍历右子树、根节点


中序遍历:中序遍历左子树,根结点,中序遍历右子树


例子

image.png

我们看这个题目后序遍历最右边为根结点,由中序遍历 可分为 左:EAF   右:HCBGI


看左边的序列 EAF ,而在后序遍历那为EFA,可知A为“根结点”,左:E   右:F


看右边的序列HCBGI,前序遍历那为HCIGB,可知B为“根结点”,左:HC  右:GI


最后可知 H在左,C在右,G在左 ,I 在右

image.png


层序遍历+中序遍历序列

image.png 开始时知道D在层序序列为第一个遍历所以,D为根结点,左子树:EAF,右子树:HCBGI

image.png

之后由中序遍历层序遍历知A为左子树的根结点,B为右子树的根结点,然后不难知A的左孩子为   E,右孩子为F。

image.png由层序遍历知,EF后面为CG所以它俩在中间,C 和 G 分别在中间,在看中序遍历序列

C的左边挂H,G的右边挂I

image.png


相关文章
|
6月前
|
算法 Java
Java数据结构与算法:用于处理不相交集合的合并和查找问题
Java数据结构与算法:用于处理不相交集合的合并和查找问题
|
6月前
|
算法
数据结构和算法学习记录——认识二叉搜索树及二叉搜索树的查找操作(递归以及迭代实现-查找操作、查找最大和最小元素)
数据结构和算法学习记录——认识二叉搜索树及二叉搜索树的查找操作(递归以及迭代实现-查找操作、查找最大和最小元素)
56 0
|
7月前
|
Python Java Go
Python每日一练(20230421) 组合总和II、加一、中后序遍历构造二叉树
Python每日一练(20230421) 组合总和II、加一、中后序遍历构造二叉树
47 0
Python每日一练(20230421) 组合总和II、加一、中后序遍历构造二叉树
|
7月前
|
算法
每日一题——排序链表(递归 + 迭代)
每日一题——排序链表(递归 + 迭代)
|
算法
代码随想录算法训练营第十八天 | 力扣 513. 找树左下角的值、112. 路径总和、113. 路径总和 II、106. 从中序与后序遍历序列构造二叉树、105. 从前序与中序遍历序列构造二叉树
代码随想录算法训练营第十八天 | 力扣 513. 找树左下角的值、112. 路径总和、113. 路径总和 II、106. 从中序与后序遍历序列构造二叉树、105. 从前序与中序遍历序列构造二叉树
57 0
|
存储 算法
算法训练Day18|● 513.找树左下角的值● 112. 路径总和 113.路径总和ii● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树
算法训练Day18|● 513.找树左下角的值● 112. 路径总和 113.路径总和ii● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树
二叉树习题系列1--将二叉搜索树排序树转化为双向链表
二叉树习题系列1--将二叉搜索树排序树转化为双向链表
|
算法 容器
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力(下
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力
90 0
|
算法 UED 容器
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力(上)
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力
123 0