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

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

目录

前序遍历 + 中序遍历序列

后序+中序遍历序列

层序遍历+中序遍历序列


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

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


相关文章
|
10月前
力扣203移除链表元素:思路分析+代码实现+方法总结(伪头节点法&递归)
力扣203移除链表元素:思路分析+代码实现+方法总结(伪头节点法&递归)
50 0
|
5月前
|
算法
数据结构单链表之查找链表的长度(迭代和递归) | 第七套
数据结构单链表之查找链表的长度(迭代和递归) | 第七套
40 0
|
6月前
|
存储 算法
【算法与数据结构】二叉树的三种遍历代码实现(上)—— 用递归序知识点讲解
【算法与数据结构】二叉树的三种遍历代码实现(上)—— 用递归序知识点讲解
28 0
|
6月前
|
算法
代码随想录算法训练营第十八天 | 力扣 513. 找树左下角的值、112. 路径总和、113. 路径总和 II、106. 从中序与后序遍历序列构造二叉树、105. 从前序与中序遍历序列构造二叉树
代码随想录算法训练营第十八天 | 力扣 513. 找树左下角的值、112. 路径总和、113. 路径总和 II、106. 从中序与后序遍历序列构造二叉树、105. 从前序与中序遍历序列构造二叉树
33 0
|
9月前
|
存储 算法
算法训练Day18|● 513.找树左下角的值● 112. 路径总和 113.路径总和ii● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树
算法训练Day18|● 513.找树左下角的值● 112. 路径总和 113.路径总和ii● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树
|
11月前
|
算法 UED 容器
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力(上)
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力
85 0
|
11月前
|
算法 容器
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力(下
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力
59 0
LeetCode——遍历序列构造二叉树
LeetCode——遍历序列构造二叉树
|
11月前
|
存储 算法 索引
LeetCode算法小抄--二叉树的各种构造
LeetCode算法小抄--二叉树的各种构造
|
12月前
如何根据二叉树的两种遍历方式重建二叉树(理论篇)
如何根据二叉树的两种遍历方式重建二叉树(理论篇)
69 0