当前位置:网站首页>二叉树的四种遍历方应用
二叉树的四种遍历方应用
2020-11-08 15:22:00 【osc_03803522】
前言
上一章我们从0
到1
的实现了一颗二叉搜索树,以及理解了二叉搜索树的特性与基本操作,这一章介绍关于二叉树的更多操作,也就是树的遍历,对树的每个节点进行访问。主要包括前序遍历、中序遍历、后序遍历、层序遍历,前面三种也叫深度优先遍历(DFS)
,最后的层序遍历也叫广度优先遍历(BFS)
,理解这四种遍历方式的不同,再遇到树相关的算法问题时,也就能更加游刃有余。这里不单指二叉搜索树,遍历思想同样适用于多叉树。
深度优先遍历(DFS)
深度优先顾名思义,首先从树的深度开始,也就是优先访问完其中一棵子树,然后再去访问另一颗子树。树的深度优先里又分为前/中/后序遍历,它们的区别仅仅是当访问到具体的节点时,它们先后顺序的不同。深度优先一般都是采用递归的方式实现,因为好理解,当然也可以使用遍历实现,不过那样会增加代码复杂性以及代码的语义化。(LeetCode上后序遍历的非递归实现可是困难难度)
前序遍历
也就是靠前访问到树的节点,首先贴出代码,给上一章实现的二叉搜索树增加前序遍历的方法:
使用一个prev
变量缓存上一次访问的节点,每一次让当前访问到的节点值减去之前节点的值,因为是中序遍历,所以当前节点的值一定是大于之前节点的,将整颗树遍历完,返回两两相减最小的值即可。
后序遍历
也是仅仅改变访问节点的位置即可,先访问左子树,再访问右子树,最后访问自身根节点,贴代码:
class BST {
constructor() {
this.root = null // 根节点
}
...
postorder(fn) { // 后序遍历
const _helper = node => {
if (!node) {
return
}
_helper(node.left) // 先访问左孩子
_helper(node.right) // 然后访问右孩子
fn(node.val) // 最后访问根节点
}
_helper(root)
}
}
先访问完左子树,然后是右子树,最后是自身节点,访问顺序如下:
后序遍历应用 - 563-二叉树的坡度
给定一个二叉树,计算整个树的坡度。
一个树的节点的坡度定义即为,该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
整个树的坡度就是其所有节点的坡度之和。
简单来说就是每个节点的坡度等于它左右子树和的绝对差,所以叶子节点的坡度就是0
,因为左右孩子都是空节点,返回的就是0-0
的值。进行子问题拆解的话,可以理解为整颗树的坡度就是它的左右子树坡度之和,所以需要先求出左右孩子的坡度才能计算出当前节点的坡度,后序遍历非常适合。
解题代码如下:
var findTilt = function (root) {
let tilt = 0
const _helper = (node) => {
if (!node) {
return 0 // 叶子节点的坡度为0
}
const l = _helper(node.left) // 先求出左子树的和
const r = _helper(node.right) // 再求出右子树的和
tilt += Math.abs(l - r) // 当前节点的坡度等于左右子树和的绝对差
return l + r + node.val // 返回子树和
}
_helper(root)
return tilt
};
深度优先遍历(DFS)应用进阶
以上三道算法题,分别展示了树的前/中/后序遍历的实际应用,这些还远远不够。有的算法题常规的遍历方式并不能太好解决问题,这个时候就需要在深刻理解了树的(DFS)
遍历特性后,进行额外灵活的处理来解决。
反常规中序遍历 - 538-把二叉搜索树转换为累加树
给定一个二叉搜索树,把它转换成为累加树,使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
题目不好懂,不过从转换的示例可以看出,从右子树最右叶子节点开始,进行两两的节点值累加,最终从右到左的累加完整棵树。如果把这颗二叉搜索树看成是一个数组[7,10,12,15,22,26,37]
,那么它的操作就是数组从后往前的进行两两相加并覆盖前一个值。对于树的话,我们就需要进行反常规的中序遍历,首先遍历右子树,然后遍历根节点,最后遍历左子树,也就是进行一次降序遍历。
var convertBST = function (root) {
let sum = 0
const _helper = (node) => {
if (!node) {
return null
}
_helper(node.right) // 先遍历右子树
node.val += sum // 右子树到底后逐个节点进行值的累加与覆盖
sum = node.val // 记录的就是上个被覆盖节点的值
_helper(node.left) // 最后遍历左子树
}
_helper(root)
return root // 返回新的累加树
};
前序加后序遍历 - 257-二叉树的所有路径
给定一个二叉树,返回所有从根节点到叶子节点的路径。
题目的要求是从根节点到叶子节点,所以要记录每一步的当前节点,而前序遍历的顺序正好可以记录从根到叶子节点的整条路径。而这道题有意思的地方在于前序遍历返回时,需要把最后一步的叶子节点从路径里移除掉,重新添加另外的节点路径值,所以可以在后序遍历的顺序里,像贪吃蛇一样一口口的去吃掉已经访问过的路径。有人把这种解法取了个挺厉害的名叫回溯。代码如下:
版权声明
本文为[osc_03803522]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4797210/blog/4708210
边栏推荐
- 浅谈,盘点历史上有哪些著名的电脑病毒,80%的人都不知道!
- Flink从入门到真香(7、Sink数据输出-文件)
- Rust: performance test criteria Library
- 一文读懂机器学习“数据中毒”
- The network adapter could not establish the connection
- . net large data concurrency solution
- Rabbitmq (1) - basic introduction
- Improvement of rate limit for laravel8 update
- Windows下快递投递柜、寄存柜的软件初探
- wanxin finance
猜你喜欢
I used Python to find out all the people who deleted my wechat and deleted them automatically
The network adapter could not establish the connection
2020-11-05
Alibaba cloud accelerates its growth and further consolidates its leading edge
3、 The parameters of the function
为什么 Schnorr 签名被誉为比特币 Segwit 后的最大技术更新
android基础-CheckBox(复选框)
Introduction to mongodb foundation of distributed document storage database
B站stm32视频学习
wanxin finance
随机推荐
区块链周报:数字货币发展写入十四五规划;拜登邀请MIT数字货币计划高级顾问加入总统过渡团队;委内瑞拉推出国营加密交易所
laravel8更新之速率限制改进
阿里云视频云技术专家 LVS 演讲全文:《“云端一体”的智能媒体生产制作演进之路》
小米、OPPO在欧洲市场继续飙涨,小米更是直逼苹果
适合c/c++新手学习的一些项目,别给我错过了!
阿里云加速增长,进一步巩固领先优势
Tencent, which is good at to C, how to take advantage of Tencent's cloud market share in these industries?
DeepMind 最新论文解读:首次提出离散概率树中的因果推理算法
别再在finally里面释放资源了,解锁个新姿势!
供货紧张!苹果被曝 iPhone 12 电源芯片产能不足
android基础-CheckBox(复选框)
数据库连接报错之IO异常(The Network Adapter could not establish the connection)
阿里云的MaxCompute数加(原ODPS)用的怎样?
Gopherchina 2020 Conference
模板引擎的整理归纳
漫画|讲解一下如何写简历&项目
我用 Python 找出了删除我微信的所有人并将他们自动化删除了
优化if-else代码的八种方案
WLAN 直连(对等连接或 P2P)调研及iOS跨平台调研
This paper analyzes the top ten Internet of things applications in 2020!