递归

前言

递归是做 LeetCode 常用的一种解法。虽然很多题目你事后看题解容易看明白，但是当你自己一开始尝试去做的时候，有时候就是另外一回事了。

今天在刷题时，看到一个题解中放了一篇文章 三道题套路解决递归问题，阅读之后有种醍醐灌顶的感觉，以下做个简单的总结。

理解递归

什么是递归？就是一个方法中会再去调用自己。

递归图示

解决递归问题时，我以前也常常容易将思维发散，去纠结于调用自身之后的逻辑流程中去。这就会让我们脑子崩溃掉，因为顺着这种思路下去，人脑就会很难理清了。

上面文章中提到了一个很重要的点：

只需要关注本级递归的解决过程即可。

做几道递归题目之后，我发现这句话对于快速解题是至关重要的！它让你跳出了正常的思维旋涡，而让你解决递归问题时将问题简化，提醒你仅关注本级问题。

比如在练习 104-Maximum Depth of Binary Tree/二叉树的最大深度 这道题时，我一开始还是陷入了思维误区中。

二叉树

需要将你的思维停在二叉树的本级上，不要再向下一级、下一级的下一级……去思考。去解这道题时，你就只需要关注本级的最大深度值怎么取？

• 如果我这一级是个空，那么，树深度是 0；—— 终止条件

• 如果我这一级不是空，那么，我的最大深度就是我左节点的最大深度、右节点最大深度，二者的最大值，然后+1 即可获取我的最大深度 —— 本级的步骤

一旦将思维跳出来之后，那么，这道题的解法就出来了。

递归题解套路

1. 递归的终止条件：终止条件要考虑全面，不仅要考虑满足条件时的终止条件，还要考虑边界条件不满足时也要终止，例如79 题，我自己理解解题时，条件顺序写错都有可能错误；

2. 返回值：应该给上一级返回什么信息；

3. 本级递归应该做什么：将思维集中在本层级，切勿进入思维误区；

接下来，就是多练、多思考、多总结、多分享！

联系

在 LeetCode 题解中也提到了一个经验：

树的问题通常可以用递归解决！