递归思路讲解
最近刷到了树这一模块的算法题,树相关的算法题几乎都是用递归来实现的,但递归的思路却有点抽象,每次遇到递归,都是通过递归来深度或广度地遍历树,但对于递归遍历树的遍历路线,却有点抽象难懂,不知道遍历的路线是怎么样的,也对于返回的路线有点懵懂。
虽然知道是用递归,也知道递归可以一层一层从上到下地遍历,大体上的一个遍历路线是明白的,但是真要将递归一层层拆解分析的话,我还是有点不知所措的,所以今天研究了一小时,彻底将递归的一层层遍历拆解分析透彻了。
记录一下拆解分析的过程,以防之后又忘了,方便回顾。

拿上面这棵树来分析,遍历的代码是:
private void dfs(TreeNode root, int depth) {if (root == null) {return;}// 先访问 当前节点,再递归地访问 右子树 和 左子树。if (depth == res.size()) { // 如果当前节点所在深度还没有出现在res里,说明在该深度下当前节点是第一个被访问的节点,因此将当前节点加入res中。res.add(root.val);}depth++;dfs(root.right, depth);dfs(root.left, depth);}
这里将 dfs(root,0)一层层地拆解分析:
1.首先传入树的根节点root,和depth = 0
2.进入方法先判断root 是否为null, 为null 则return,这里也是后面递归的终止条件,当遍历到叶子结点下一节点时返回上一层。
3.进入到dfs(root.right,depth)递归环节,root.right = 1,depth = 0
(1)先判断root.right 是否为null,这里不为null,root.right = 3 ,depth = 1
(2)继续向下递归,先判断root.right.right 是否为null,这里不为null,root.right.right = 6 ,depth = 2
(3)继续向下递归,先判断root.right.right.right是否为null,这里为null,则return到上一层,跳到root.right.right = 6 ,depth = 2这一层
(4)在root.right.right = 6 ,depth = 2这一层,dfs(root.right.right.right,depth)已结束,执行下一句dfs(root.right.right.left,depth),进入方法后判断是否为null,不为null,root.right.right.left = 8,depth = 3
(5)在root.right.right.left = 8,depth = 3这一层,分别递归右子树和左子树,都为null,则返回root.right.right.left = 8,depth = 3这一层;同时root.right.right = 6 ,depth = 2这一层已经全部结束,返回到了root.right = 3 ,depth = 1这一层
(6)在root.right = 3 ,depth = 1这一层,右子树已经遍历完毕,开始遍历左子树dfs(root.right.right,depth),左子树为null,则root.right = 3 ,depth = 1这一层的左右子树也已经遍历完毕,所以回到了root.right = 1,depth = 0
4.此时dfs(root.right,depth)这句代码已经全部执行完毕,到了dfs(root.left,depth)这句话的执行,root.left = 2,depth = 1,然后像第3步一样开始从右子树--->左子树地递归
思路其实就像是套娃一样,一个大的盒子里装了两个小的套娃,这两个套娃里分别装着一层层的套娃,我们要先结束一个大的套娃,再结束另一个大的套娃。
如果文字看的比较抽象,可以参考这个视频辅助理解:
递归算法很难?小s带你10分钟完成手把手推导,用递归求二叉树深度
相关文章:
递归思路讲解
最近刷到了树这一模块的算法题,树相关的算法题几乎都是用递归来实现的,但递归的思路却有点抽象,每次遇到递归,都是通过递归来深度或广度地遍历树,但对于递归遍历树的遍历路线,却有点抽象难懂,不…...
基于R语言APSIM模型高级应用及批量模拟
目录 专题一 APSIM模型应用与R语言数据清洗 专题二 APSIM气象文件准备与R语言融合应用 专题三 APSIM模型的物候发育和光合生产模块 专题四 APSIM物质分配与产量模拟 专题五 APSIM土壤水平衡模块 专题六 APSIM土壤碳、氮平衡模块 专题七 APSIM农田管理模块与情景模拟 专…...
Hyperf中的其它事项
Hyperf中的其它事项 关于 Hyperf 其它的内容我们就不多说了,毕竟框架这东西用得多了自然也就熟悉了。最重要的是——我的水平还不足以去深入地分析这个框架! 好吧,其它的功能大家可以去官方文档详细了解,毕竟国人自己做的框架&a…...
【技术选型】Elasticsearch 和Solr那个香?
我们为什么在这里?我存在的目的是什么?我应该运动还是休息并节省能量?早起上班或晚起并整夜工作?我应该将炸薯条和番茄酱或蛋黄酱一起吃吗? 这些都是古老的问题,可能有也可能没有答案。其中一些是非常困难或…...
4面美团测试工程师,因为这个小细节,直接让我前功尽弃.....
说一下我面试别人时候的思路 反过来理解,就是面试时候应该注意哪些东西;用加粗部分标注了 一般面试分为这么几个部分: 一、自我介绍 这部分一般人喜欢讲很多,其实没必要。大约5分钟内说清楚自己的职业经历,自己的核…...
数据恢复软件EasyRecovery16下载安装步骤教程
EasyRecovery16是一款专业好用的数据恢复软件,软件提供了向导式的操作向导,可以有效地恢复电脑或者移动存储设备中丢失的各种文件,包括删除的文件、格式化丢失的文件和清空回收站的数据!千呼万唤始出来,大家期盼许久的EasyRecover…...
Springboot 自定义缓存配置 CacheManager 及redis集成
目录 前言 集成 maven依赖 CacheManagerConfig配置 redis配置 使用 Springboot 集成使用缓存 Cacheable CacheEvict 前言 现有项目中经常遇到的缓存集成问题,Springboot提供了统一的接口抽象与缓存管理器,可集成多种缓存类型,如 Co…...
JS 中七个改变原数组的方法
目录 一、push 二、pop 三、unshift 四、shift 五、splice 六、sort 七、reverse 一、push 在数组的尾部添加元素,并返回新的长度。 let arr [1] arr.push(2) console.log(arr) // [1, 2] 二、pop 删除数组最后面一个元素、并返回删除的元素。 let arr [1, …...
【笔试强训选择题】Day7.习题(错题)解析
作者简介:大家好,我是未央; 博客首页:未央.303 系列专栏:笔试强训选择题 每日一句:人的一生,可以有所作为的时机只有一次,那就是现在!!! 文章目录…...
Vue电商项目--axios二次封装
postman测试接口 刚刚经过postman工具测试,发现接口果然发生了改变。 新的接口为http://gmall-h5-api.atguigu.cn 如果服务器返回的数据code字段200,代表服务器返回数据成功 整个项目,接口前缀都有/api字样 axios二次封装 XmlHttpRequ…...
人生四维度
人生四维度 不是有钱了就成功,你知道;人生的成功不止一种,你也知道。但成功还有哪种?你知道吗? 如果把人生的体验展开,我们可以得到四个维度,高度、深度、宽度和温度。 财富、权力、影响力 构…...
Python 调用 MessageBeep 播放系统音效
Python 调用 MessageBeep 播放 Windows 系统提示声音 Windows API 函数 "MessageBeep" 介绍 "Windows API MessageBeep"是一个用于发出系统提示音效的函数。它可以向用户发出一种预定义的声音,以指示事件的发生或某个条件的满足。例如…...
废物,我TMD一个985却斗不过专科生(大厂自动化测试2年被裁)
前言 看到标题,可能很多读者朋友恐怕又要骂我了,985这个特殊的字眼也确实异常晃眼,实际上现在985,211也越来越多,它能代表你能够进入到更高的平台,拿到“高级工厂”的入场券,但并不意味着你会成…...
p70 内网安全-域横向内网漫游 Socks 代理隧道技术(NPS、FRP、CFS 三层内网漫游)
数据来源 本文仅用于信息安全学习,请遵守相关法律法规,严禁用于非法途径。若观众因此作出任何危害网络安全的行为,后果自负,与本人无关。 必要基础知识点: 内外网简单知识内网 1 和内网 2 通信问题正向反向协议通…...
第三十二章 Unity Mecanim动画系统(上)
在上一章节中,我们介绍了Unity的旧版动画系统,本章节来介绍新版的Mecanim动画系统。新版的Mecanim动画系统实际是对旧版动画系统的升级。新版的Mecanim动画系统仍然是建立在动画片段的基础上的,只不过它给我们提供了一个可视化的窗口来编辑动…...
第二章 集合
系列文章目录 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 例如:第一章 Python 机器学习入门之pandas的使用 提示:写完文章后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目…...
这一篇Databinding应该可以帮助迅速上手吧
Databinding使用篇(迅速上手) 使用前需要在模块级别的build.gradle里面的android闭包里添加: dataBinding{enabled true}接着在layout文件中按下Alt 回车, 将布局转换成data binding layout即可,此时编译就会生成对…...
【PHP在线定制商城网站源码V3.0】开源的DIY在线定制商城系统+在线礼品定制
源码下载:https://download.csdn.net/download/m0_66047725/87637177 PHP在线定制商城网站源码,免费开源、免费下载。本商城基于mycncart开发。安装成功后即可浏览,你可以在后台->安装扩展功能上传安装插件,在代码调整中点击刷…...
cout源码浅析
目录 cout源码浅析 那么对于没有定义在这之中的要怎么办呢? 实际使用 结语 首先来看我从cplusplus中截取的这张图: 注意最下面这一行字。cout其实是ostream的一个标准对象object。而上面则演示了一些继承关系。 好的,理解了之后…...
发送Ajax get请求详解
发送AJAX get请求,前端代码: <!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8"> <title>ajax get请求</title> </head> <body> <script type"text/java…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文通过代码驱动的方式,系统讲解PyTorch核心概念和实战技巧,涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...
【Veristand】Veristand环境安装教程-Linux RT / Windows
首先声明,此教程是针对Simulink编译模型并导入Veristand中编写的,同时需要注意的是老用户编译可能用的是Veristand Model Framework,那个是历史版本,且NI不会再维护,新版本编译支持为VeriStand Model Generation Suppo…...
前端开发者常用网站
Can I use网站:一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use:Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站:MDN JavaScript权威网站:JavaScript | MDN...
门静脉高压——表现
一、门静脉高压表现 00:01 1. 门静脉构成 00:13 组成结构:由肠系膜上静脉和脾静脉汇合构成,是肝脏血液供应的主要来源。淤血后果:门静脉淤血会同时导致脾静脉和肠系膜上静脉淤血,引发后续系列症状。 2. 脾大和脾功能亢进 00:46 …...
