如何使用递归三步走解决leetcode算法题，附三道例题
递归
何为递归？程序反复调用自身即是递归。
我自己在刚开始解决递归问题的时候，总是会去纠结这一层函数做了什么，它调用自身后的下一层函数又做了什么…然后就会觉得实现一个递归解法十分复杂，根本就无从下手。
这是一个思维误区，一定要走出来。既然递归是一个反复调用自身的过程，这就说明它每一级的功能都是一样的，因此我们只需要关注一级递归的解决过程即可。
我们需要关心的主要是以下三点：
- 整个递归的终止条件。
- 一级递归需要做什么？
- 应该返回给上一级的返回值是什么？
因此，也就有了我们解递归题的三部曲：
- 找整个递归的终止条件：递归应该在什么时候结束？
- 找返回值：应该给上一级返回什么信息？
- 本级递归应该做什么：在这一级递归中，应该完成什么任务？
一个生动的例子：
递归是算法设计中的一种基本而重要的算法。递归方法通过函数调用自身将问题转化为本质相同但规模较小的子问题，是分治策略的具体体现。
递归算法的定义：如果一个对象的描述中包含它本身，我们就称这个对象是递归的，这种用递归来描述的算法称为递归算法。
先来看看大家熟知的一个的故事： 从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，老和尚讲：从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，老和尚讲：…… 上面的故事本身是递归的，用递归算法描述：
void bonze-tell-story(){
if(讲话被打断){
故事结束;
return;
}
从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事；
bonze-tell-story();
}
从上面的递归事例不难看出，递归算法存在的两个必要条件：
- 必须有递归的终止条件，如老和尚的故事一定要在某个时候应该被打断，可以是小和尚听烦了叫老和尚停止，或老和尚本身就只想重复讲10遍等；
- 过程的描述中包含它本身。
递归是一种非常有用的程序设计技术。当一个问题蕴含递归关系且结构比较复杂时，采用递归算法往往比较自然、简洁、容易理解。
递归思想的基本思想是把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。用递归思想写出的程序往往十分简洁易懂。 一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
使用递归要注意以下几点：
（1）递归就是在过程或函数里调用自身；
（2）在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
例1：求二叉树的最大深度
一道简单的Leetcode题目： Leetcode 104. 二叉树的最大深度
题目很简单，求二叉树的最大深度，那么直接套递归解题三部曲模版：
- 找终止条件。 什么情况下递归结束？当然是树为空的时候，此时树的深度为0，递归就结束了。
- 找返回值。 应该返回什么？题目求的是树的最大深度，我们需要从每一级得到的信息自然是当前这一级对应的树的最大深度，因此我们的返回值应该是当前树的最大深度，这一步可以结合第三步来看。
- 本级递归应该做什么。 首先，还是强调要走出之前的思维误区，递归后我们眼里的树一定是这个样子的，此时就三个节点：root、root.left、root.right，其中根据第二步，root.left和root.right分别记录的是root的左右子树的最大深度。那么本级递归应该做什么就很明确了，自然就是在root的左右子树中选择较大的一个，再加上1就是以root为根的子树的最大深度了，然后再返回这个深度即可。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
// 终止条件：当树为空时结束递归，并返回当前深度0
if (root == nullptr) {
return 0;
}
// root的左、右子树的最大深度
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
// 返回的是左右子树的最大深度+1
return max(leftDepth, rightDepth) + 1;
}
};
当足够熟练后，也可以和Leetcode评论区一样，很骚的几行代码搞定问题，让之后的新手看的一脸懵逼。
class Solution {
public:
int maxDepth(TreeNode* root) {
return root == nullptr ? 0 : max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
例2：两两交换链表中的节点
看了一道递归套路解决二叉树的问题后，有点套路搞定递归的感觉了吗？我们再来看一道Leetcode中等难度的链表的问题，掌握套路后这种中等难度的问题真的就是秒：Leetcode 24. 两两交换链表中的节点
直接上三部曲模版：
- 找终止条件。 什么情况下递归终止？没得交换的时候，递归就终止了呗。因此当链表只剩一个节点或者没有节点的时候，自然递归就终止了。
- 找返回值。 我们希望向上一级递归返回什么信息？由于我们的目的是两两交换链表中相邻的节点，因此自然希望交换给上一级递归的是已经完成交换处理，即已经处理好的链表。
- 本级递归应该做什么。 结合第二步，由于只考虑本级递归，所以这个链表在我们眼里其实也就三个节点：head、head.next、已处理完的链表部分。而本级递归的任务也就是交换这3个节点中的前两个节点，就很easy了。
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
// 终止条件：链表只剩一个节点或者没节点了，没得交换了。返回的是已经处理好的链表
if (head == nullptr || head->next == nullptr) {
return head;
}
// 一共三个节点:head, next, swapPairs(next.next)
// 下面的任务便是交换这3个节点中的前两个节点
ListNode* next = head->next;
head->next = swapPairs(next->next);
next->next = head;
// 根据第二步：返回给上一级的是当前已经完成交换后，即处理好了的链表部分
return next;
}
};
例3：平衡二叉树
相信经过以上2道题，你已经大概理解了这个模版的解题流程了。
那么请你先不看以下部分，尝试解决一下这道easy难度的Leetcode题（个人觉得此题比上面的medium难度要难）：Leetcode 110. 平衡二叉树
我觉得这个题真的是集合了模版的精髓所在，下面套三部曲模版：
-
找终止条件。 什么情况下递归应该终止？自然是子树为空的时候，空树自然是平衡二叉树了。
-
应该返回什么信息：
为什么我说这个题是集合了模版精髓？正是因为此题的返回值。要知道我们搞这么多花里胡哨的，都是为了能写出正确的递归函数，因此在解这个题的时候，我们就需要思考，我们到底希望返回什么值？
何为平衡二叉树？平衡二叉树即左右两棵子树高度差不大于1的二叉树。而对于一颗树，它是一个平衡二叉树需要满足三个条件：它的左子树是平衡二叉树，它的右子树是平衡二叉树，它的左右子树的高度差不大于1。换句话说：如果它的左子树或右子树不是平衡二叉树，或者它的左右子树高度差大于1，那么它就不是平衡二叉树。
而在我们眼里，这颗二叉树就3个节点：root、left、right。那么我们应该返回什么呢？如果返回一个当前树是否是平衡二叉树的boolean类型的值，那么我只知道left和right这两棵树是否是平衡二叉树，无法得出left和right的高度差是否不大于1，自然也就无法得出root这棵树是否是平衡二叉树了。而如果我返回的是一个平衡二叉树的高度的int类型的值，那么我就只知道两棵树的高度，但无法知道这两棵树是不是平衡二叉树，自然也就没法判断root这棵树是不是平衡二叉树了。
因此，这里我们返回的信息应该是既包含子树的深度的int类型的值，又包含子树是否是平衡二叉树的boolean类型的值。可以单独定义一个ReturnNode类，如下：
class ReturnNode{ bool isB; int depth; //构造方法 public ReturnNode(boolean isB, int depth){ this->isB = isB; this->depth = depth; } } -
本级递归应该做什么。 知道了第二步的返回值后，这一步就很简单了。目前树有三个节点：root，left，right。我们首先判断left子树和right子树是否是平衡二叉树，如果不是则直接返回false。再判断两树高度差是否不大于1，如果大于1也直接返回false。否则说明以root为节点的子树是平衡二叉树，那么就返回true和它的高度。
class Solution {
// 这个ReturnNode是参考我描述的递归套路的第二步：思考返回值是什么
// 一棵树是BST等价于它的左、右俩子树都是BST且俩子树高度差不超过1
// 因此我认为返回值应该包含当前树是否是BST和当前树的高度这两个信息
private:
class ReturnNode {
public:
bool isB;
int depth;
ReturnNode(int depth, bool isB) {
this->isB = isB;
this->depth = depth;
}
};
// 主函数
public:
bool isBalanced(TreeNode* root) { return isBST(root)->isB; }
// 参考递归套路的第三部：描述单次执行过程是什么样的
// 这里的单次执行过程具体如下：
// 是否终止?->没终止的话，判断是否满足不平衡的三个条件->返回值
ReturnNode* isBST(TreeNode* root) {
if (root == nullptr) {
return new ReturnNode(0, true);
}
// 不平衡的情况有3种：左树不平衡、右树不平衡、左树和右树差的绝对值大于1
ReturnNode* left = isBST(root->left);
ReturnNode* right = isBST(root->right);
if (!left->isB || !right->isB || abs(left->depth - right->depth) > 1) {
return new ReturnNode(0, false);
}
// 不满足上面3种情况，说明平衡了，树的深度为左右俩子树最大深度+1
return new ReturnNode(std::max(left->depth, right->depth) + 1, true);
}
};