当前位置: 首页 > 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…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...