🚀个人主页：一颗小谷粒

🚀所属专栏：力扣刷题

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

目录

💥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