一篇文章带你搞定所有二叉树题型的递归思维(思路超详细)

文章目录

  • 🎀前言:
    • 🏅先在开头总结一下,二叉树解题的思维模式分两类:
    • 🎇先解释一下“前序位置”,“后序位置”的意思
      • 🏨举一个简单的例子:
  • 🪀下面通过两道例题,让你更加清晰的认识一下:
    • 示例一:求二叉树的最大高度
    • 示例二:翻转二叉树

🎀前言:

本篇博客目的是为了培养面对二叉树题型解题思维及去让你充分理解每个结点在递归之前、递归之后的位置的不同作用

🏅先在开头总结一下,二叉树解题的思维模式分两类:

这里是引用

🎇先解释一下“前序位置”,“后序位置”的意思

在这里插入图片描述
你也注意到了,只要是递归形式的遍历,都可以有前序位置后序位置
分别在递归之前递归之后

前序位置:就是刚进入一个节点(元素)的时候,
后序位置:就是即将离开一个节点(元素)的时候,那么进一步,
你把代码写在不同位置,代码执行的时机也不同:
在这里插入图片描述

🏨举一个简单的例子:

比如说,如果让你倒序打印一条单链表上所有节点的值,你怎么搞?

这里是引用

结合上面那张图,你应该知道为什么这段代码能够倒序打印单链表了吧。
那如果让你正序打印呢?

这里是引用

如过你理解了,那么恭喜你,你已经理解真谛了。那么二叉树也是一样的,它就只是多了一个叉而已
在这里插入图片描述
讲了这么多,这就是所有的核心内容了。,接下来就是如何来用,如何将这个知识带入做题思维里边去,就行了。
在这里插入图片描述

🪀下面通过两道例题,让你更加清晰的认识一下:

示例一:求二叉树的最大高度

在这里插入图片描述
你做这题的思路是什么?
显然遍历一遍二叉树,用一个外部变量记录每个节点所在的深度,
取最大值就可以得到最大深度了,这就是遍历二叉树计算答案的思路。
在这里插入图片描述

这个解法应该很好理解,但为什么需要在前序位置增加 depth,在后序位置减小 depth?

因为前面说了,前序位置是进入一个节点的时候,后序位置是离开一个节点的时候,
depth 记录当前递归到的节点深度,你把 traverse 理解成在二叉树上游走的一个指针,
所以当然要这样维护。

至于对 res 的更新,你放到前中后序位置都可以,只要保证在进入节点之后,
离开节点之前(即 depth 自增之后,自减之前)就行了。(优化部分,是考虑到每次递归都需要更新res的值,而树的最大高度是根到叶子节点中最深的)

🐕当然,你也很容易发现一棵二叉树的最大深度可以通过子树的最大深度推导出来,
这就是分解问题计算答案的思路

在这里插入图片描述
因为这个思路正确的核心在于,你确实可以通过子树的最大深度推导出原树的深度,
所以当然要首先利用递归函数的定义算出左右子树的最大深度,然后推出原树的最大深度,
主要逻辑自然放在后序位置
在这里插入图片描述

示例二:翻转二叉树

在这里插入图片描述

不难发现,只要把二叉树上的每一个节点的左右子节点进行交换,最后的结果就是完全翻转之后的二叉树。

那么现在开始在心中默念二叉树解题总纲:

1、这题能不能用「遍历」的思维模式解决?

可以,我写一个 traverse 函数遍历每个节点,让每个节点的左右子节点相互交换过来就行了
在这里插入图片描述

2、这题能不能用「分解问题」的思维模式解决?

可以,从叶子节点入手,先交换叶子节点的左右子树,
再进行倒数第二层父节点处理操作(这里假设它是棵满二叉树),
交换左右子树的叶子节点,再进行倒数第三层父节点处理操作,交换它的左右子树,…
直到根节点,交换它的左右子树
在这里插入图片描述

至此,我们在面对二叉树的所有问题时,都能够有思路了。
甚至你一眼就能看出别人用的是遍历二叉树的思路还是分解成左右子树来推出结果的思路
(主要看它的逻辑操作在‘前序位置’还是‘后序位置’写了,它就是哪种思路)

能够看到这里的朋友,谢谢你能够坚持看完,如果这个思维框架对你有所启发,
推荐你看一下《labuladong的算法笔记》(或者直接在哔站上看他讲的网课(讲的挺好的))

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/161233.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

从自动化到测开,测试人员逆袭之路从此起步

在当今竞争激烈的软件测试行业中,近期的招聘市场确实面临一些挑战。大量的求职者争相涌入岗位,许多热衷于功能测试的人士甚至难以找到理想的工作机会。更不幸的是,连自动化测试和性能测试这些专业领域也受到了测试开发人员的竞争压力。然而&a…

C# 图解教程 第5版 —— 第4章 类型、存储和变量

文章目录 4.1 C# 程序是一组类型声明4.2 类型是一种模板(*)4.3 实例化类型4.4 数据成员和函数成员4.5 预定义类型4.6 用户定义类型4.7 堆和栈(*)4.8 值类型和引用类型4.9 变量4.9.1 变量声明4.9.2 多变量声明(*&#x…

模式植物背景基因集制作

一边学习,一边总结,一边分享! 写在前面 关于GO背景基因集文件的制作,我们在很早以前也发过。近两天,自己在分析时候,也是被搞了头疼。想重新制作一份GO背景基因集,进行富集分析。但是结果&…

排序【七大排序】

文章目录 1. 排序的概念及引用1.1 排序的概念1.2 常见的排序算法 2. 常见排序算法的实现2.1 插入排序2.1.1基本思想:2.1.2 直接插入排序2.1.3 希尔排序( 缩小增量排序 ) 2.2 选择排序2.2.1基本思想:2.2.2 直接选择排序:2.2.3 堆排序 2.3 交换排序2.3.1冒…

uniapp小程序中给web-view页面添加授权弹窗(使用cover-view组件覆盖实现该功能)

效果图: web-view是承载网页的容器。会自动铺满整个小程序页面,个人类型的小程序暂不支持使用。 再看下面一个提示: 每个页面只能有一个 web-view,web-view 会自动铺满整个页面,并覆盖其他组件。 也就是说,…

云安全—云计算基础

0x00 前言 学习云安全,那么必然要对云计算相关的内容进行学习和了解,所以云安全会分为两个部分来进行,首先是云计算先关的内容。 0x01 云计算 广泛传播 云计算最早大范围传播是2006年,8月,在圣何塞【1】举办的SES&a…

七大排序 (9000字详解直接插入排序,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序)

一:排序的概念及引入 1.1 排序的概念 1.1 排序的概念 排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 稳定性:假定在待排序的记录序列中,存在…

DITA-OT 4.0新特性 - PDF themes,定制PDF样式的新方法

随着DITA-OT 4.0的发布,它提供了一种新的定制PDF样式方法,这种方法就是PDF theme。这篇文章来聊一聊这种定制PDF输出的新方法和实验结果。 在进入PDF theme细节之前,为各位读者梳理一下DITA-OT将DITA和Markdown发布成PDF的几种方法。 - 1 …

element ui 下拉框 选择月份和天数

一、背景 目前做的管理系统项目&#xff0c;期望实现功能为&#xff1a;设置出账周期和出账日&#xff0c;考虑使用element ui下拉框实现功能 二、所用技术 vue2element ui 三、实现效果 四、具体代码 <template><popup-frame :title"批量设置出账日" …

OJ第四篇

文章目录 链表分割环形链表有效的括号 链表分割 链接: 链表分割 虽然这个题牛客网中只有C,但是无所谓&#xff0c;我们只要知道C是兼容C的就可以了 至于说这个题的思路&#xff0c;我们就弄两个链表&#xff0c;把小于x的结点放到一个链表中&#xff0c;剩下的放到另一个链表…

2023年10月工作经验及问题整理总结

目录 1.window自带的base64加密解密 2.ElementUI修改鼠标移动到表格的背景色 3.vscode保存时几万个eslint错误 4.Git 拉取Gitee仓库报错&#xff1a;“fatal: unable to access ": Failed to connect to 127.0.0.1 port 1080: Connection r... 4.1本地查看Git是否使用…

Java版本spring cloud + spring boot企业电子招投标系统源代码

项目说明 随着公司的快速发展&#xff0c;企业人员和经营规模不断壮大&#xff0c;公司对内部招采管理的提升提出了更高的要求。在企业里建立一个公平、公开、公正的采购环境&#xff0c;最大限度控制采购成本至关重要。符合国家电子招投标法律法规及相关规范&#xff0c;以及审…

spark stream入门案例:netcat准实时处理wordCount(scala 编程)

目录 案例需求 代码 结果 解析 案例需求&#xff1a; 使用netcat工具向9999端口不断的发送数据&#xff0c;通过SparkStreaming读取端口数据并统计不同单词出现的次数 -- 1. Spark从socket中获取数据&#xff1a;一行一行的获取 -- 2. Driver程序执行时&#xff0c…

加固数据安全:Java助力保护Excel文件,让数据无懈可击

摘要&#xff1a;本文由葡萄城技术团队于CSDN原创并首发。转载请注明出处&#xff1a;葡萄城官网&#xff0c;葡萄城为开发者提供专业的开发工具、解决方案和服务&#xff0c;赋能开发者。 前言 Excel文件保护是常用的一种功能&#xff0c;文件保护主要有三种&#xff1a; 添…

单目3D自动标注

这里介绍两种 1. 基于SAM的点云标注 Seal&#xff1a;是一个多功能的自监督学习框架&#xff0c;能够通过利用视觉基础模型的现成知识和2D-3D的时空约束分割自动驾驶数据集点云 Scalability&#xff1a;可拓展性强&#xff0c;视觉基础模型蒸馏到点云中&#xff0c;避免2D和…

SaaS人力资源管理系统的Bug

SaaS人力资源管理系统的Bug Bug1【18】 这里我是直接把代码复制过来的&#xff0c;然后就有一个空白 这是因为它的代码有问题&#xff0c;原本的代码如下所示 <el-table-column fixed type"index" label"序号" width"50"></el-table…

Linux性能优化--性能追踪:受CPU限制的应用程序(GIMP)

10.0 概述 本章包含了一个例子&#xff1a;如何用Linux性能工具在受CPU限制的应用程序中寻找并修复性能问题。 阅读本章后&#xff0c;你将能够&#xff1a; 在受CPU限制的应用程序中明确所有的CPU被哪些源代码行使用。用1trace和oprofile弄清楚应用程序调用各种内部与外部函…

KNN-近邻算法 及 模型的选择与调优(facebook签到地点预测)

什么是K-近邻算法&#xff08;K Nearest Neighbors&#xff09; 1、K-近邻算法(KNN) 1.1 定义 如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别&#xff0c;则该样本也属于这个类别。 来源&#xff1a;KNN算法最早是由Cover和Hart提…

【JVM面试】从JDK7 到 JDK8, JVM为啥用元空间替换永久代?

系列文章目录 【JVM系列】第一章 运行时数据区 【面试】第二章 从JDK7 到 JDK8, JVM为啥用元空间替换永久代&#xff1f; 大家好&#xff0c;我是青花。拥有多项发明专利&#xff08;都是关于商品、广告等推荐产品&#xff09;。对广告、Web全栈以及Java生态微服务拥有自己独到…

VSS、VDD、VBAT、VSSA

引言 在学习设计TM32时&#xff0c;发现芯片除了GPIO引脚外还会引出许多引脚&#xff0c;以STM32F407ZGT6为例除了GPIO引脚还会有以下引脚 如VSS、VDD、VBAT、VSSA、NRST、VREF、VDDA、VCAP_1、VCAP_2、PDR_ON这些引脚。他们有何作用&#xff0c;电路设计中应如何连接&#x…