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

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

select、poll、epoll 与 Reactor 模式

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

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...