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

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

目录

前序遍历 + 中序遍历序列

后序+中序遍历序列

层序遍历+中序遍历序列


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

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 Go 人工智能
Java每日一练(20230502) BST公共祖先、随机分组、K个一组翻转链表
Java每日一练(20230502) BST公共祖先、随机分组、K个一组翻转链表
45 0
Java每日一练(20230502) BST公共祖先、随机分组、K个一组翻转链表
|
6月前
|
Python Java Go
Python每日一练(20230421) 组合总和II、加一、中后序遍历构造二叉树
Python每日一练(20230421) 组合总和II、加一、中后序遍历构造二叉树
46 0
Python每日一练(20230421) 组合总和II、加一、中后序遍历构造二叉树
|
12月前
|
算法
代码随想录算法训练营第十八天 | 力扣 513. 找树左下角的值、112. 路径总和、113. 路径总和 II、106. 从中序与后序遍历序列构造二叉树、105. 从前序与中序遍历序列构造二叉树
代码随想录算法训练营第十八天 | 力扣 513. 找树左下角的值、112. 路径总和、113. 路径总和 II、106. 从中序与后序遍历序列构造二叉树、105. 从前序与中序遍历序列构造二叉树
52 0
二叉树习题系列1--将二叉搜索树排序树转化为双向链表
二叉树习题系列1--将二叉搜索树排序树转化为双向链表
|
算法 容器
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力(下
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力
85 0
|
算法 UED 容器
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力(上)
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力
118 0
|
算法 Java
代码随想录训练营day23| 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树...
代码随想录训练营day23| 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树...
|
存储 算法 索引
LeetCode算法小抄--二叉树的各种构造
LeetCode算法小抄--二叉树的各种构造
如何根据二叉树的两种遍历方式重建二叉树(理论篇)
如何根据二叉树的两种遍历方式重建二叉树(理论篇)
113 0