当前位置: 首页 > news >正文

递归思路讲解

最近刷到了树这一模块的算法题,树相关的算法题几乎都是用递归来实现的,但递归的思路却有点抽象,每次遇到递归,都是通过递归来深度或广度地遍历树,但对于递归遍历树的遍历路线,却有点抽象难懂,不知道遍历的路线是怎么样的,也对于返回的路线有点懵懂。

虽然知道是用递归,也知道递归可以一层一层从上到下地遍历,大体上的一个遍历路线是明白的,但是真要将递归一层层拆解分析的话,我还是有点不知所措的,所以今天研究了一小时,彻底将递归的一层层遍历拆解分析透彻了。

记录一下拆解分析的过程,以防之后又忘了,方便回顾。

 

拿上面这棵树来分析,遍历的代码是:

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"是一个用于发出系统提示音效的函数。它可以向用户发出一种预定义的声音,以指示事件的发生或某个条件的满足。例如&#xf…...

废物,我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。而上面则演示了一些继承关系。 好的,理解了之后&#xf…...

发送Ajax get请求详解

发送AJAX get请求&#xff0c;前端代码&#xff1a; <!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8"> <title>ajax get请求</title> </head> <body> <script type"text/java…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...

sshd代码修改banner

sshd服务连接之后会收到字符串&#xff1a; SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢&#xff1f; 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头&#xff0c…...