您的位置:首页 > 科技 > IT业 > 【二叉树的最大深度】带你理解递归奥妙!

【二叉树的最大深度】带你理解递归奥妙!

2024/11/9 9:22:49 来源:https://blog.csdn.net/2301_79263365/article/details/142222677  浏览:    关键词:【二叉树的最大深度】带你理解递归奥妙!

🚀个人主页:一颗小谷粒

🚀所属专栏:力扣刷题

很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎 ~

目录

💥1.1 题目要求 

​💥1.2 算法思路

💥1.3 图解分析 

💥1.4 Java代码实现

💥1.5 复杂度分析

💥1.6 递归与栈溢出


💥1.1 题目要求 

leetcode.104 二叉树的最大深度 是一道典型的通过递归来完成的题目:

104. 二叉树的最大深度 - 力扣(LeetCode)

这道题目非常简单,大家可以先看看目录1.4 的代码实现。但是递归的含义你真的理解吗?计算机是怎么执行递归的?为什么这样写就可以算出正确答案?

接下来我以此题为例,逐步分析递归的过程:

​💥1.2 算法思路

递归的概念:

递归算法分为两大阶段 : 递和归,即就是有去(递去)有回(归来)。

  • 递去:将递归问题分解为若干个规模较小, 与原问题形式相同的子问题,这些子问题可以用相同的解题思路来解决。
  • 归来:当你将问题不断缩小规模递去的时候, 必须有一个明确的结束递去的临界点(递归出口),一旦达到这个临界点即就从该点原路返回到原点,最终问题得到解决。

递归的要素:

  • 递归终止的条件
  • 递归操作

简单来说递归就是函数自己调用自己,我们需要把我们的计算结果返给它的上一级问题,而它的上一级问题又会把计算结果返给上上一级问题。

数学归纳法:

递归其实就是数学归纳法的思想

💥1.3 图解分析 

不要一开始就陷入细节,我们的问题是有嵌套关系的。

本题中我们的递归终止条件就是空结点,遇到空结点就将结果返回给上一级,直到归到最初始的程序,也就是结点为3的时候。

💥1.4 Java代码实现

    public int maxDepth(TreeNode root) {if(root==null){return 0;}int leftDepth = maxDepth(root.left);int rightDepth = maxDepth(root.right);return Math.max(leftDepth, rightDepth)+1;}

或许到这里,有些小伙伴还是不理解这个程序的执行过程,那么可以参考下图结合代码再次分析,相信你会恍然大悟的: 

一层一层递,最后一层一层归上去,返回的就是左右子树的深度了。 

💥1.5 复杂度分析

  • 时间复杂度:O(n),其中 n 为二叉树的节点个数。
  • 空间复杂度:O(n)。最坏情况下,二叉树退化成一条链,递归需要 O(n) 的栈空间。

💥1.6 递归与栈溢出

递归的优点是可以使代码简洁、直观,尤其适用于处理具有重复子结构的问题,比如树和图的遍历等。但是,如果递归调用过深(例如没有正确设置基础情况或者处理的数据规模过大),可能会导致栈溢出错误,因为每次递归调用都会在内存中占用一定的栈空间。

递归就是系统自动帮你压栈  



屏幕前正在学习计算机的你可能正处于焦虑、迷茫、内耗的状态,但路是我们自己选择的,是自己为自己做出的决定,而对这所有的困难我们应该早就有了勇气,拿出自己的心态,拿出自己的意志,把这步走到底!因为你尝试了,即使不成功,你也迈出了一大步,请你努力 为了你自己 ! ! !

博主微信:g2279605572 

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com