递归解题核心思想
# 递归解题核心思想## 1、递归要考虑的三个问题：
> - 递归应该在什么时候结束？
> - 我应该返回什么信息给上层？
> - 在这一次的递归中，要完成什么任务？
***递归每一层的功能都是一样的***，所以只要解决了这三个问题，递归的问题就解决了
## 2、举例说明：
### 2.1、二叉树的最大深度
1、什么时候结束递归？
当遍历到树的左右节点都为空的时候，递归就结束了！
2、返回给上层的是什么？
因为是对树深度的遍历，所以返回给上层的，自然是这颗子树的深度
3、本次递归中，要完成什么任务？
每一次的递归，都是在获取树的深度，可能左右子树都存在，那么自然要返回最高的那颗树的值，同时，要加上1，因为本身的这棵树，也属于一层，当遍历到自身为null的时候，就返回0(不用+1)
4、代码如下：
```java
public int maxDepth(TreeNode root) {
if (root == null){
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return left > right ? left + 1 : right + 1;
}
```
### 2.2、两两交换链表中的节点
> 问题描述：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
1、什么时候结束递归？
当已经到了最后的元素，不能再交换了，结束递归
2、返回给上层的是什么？
交换后的链表，把两个链表进行交换后，返回给上一层
3、本次递归中，要完成什么任务？
递归值考虑一层，也就意味着，我们眼中的一条链表，分成了三个部分
head-->head.next-->已经处理好的链表部分，我们要做的，自然就是把head和head.next进行交换
4、代码实现
```java
if (head == null || head.next == null) {
return head;
}
/**
* 用temp做中间临时变量
*/
ListNode temp = head.next;
//把排序好的链表，挂到head节点的next上面
head.next = swapPairs(temp.next);
//把head，挂到临时变量的next上面
temp.next = head;
return temp;
```
### 2.3、判断二叉树是否高度平衡
1、什么时候结束递归？
当左子树或右子树不为平衡二叉树时，或遍历完所有节点
2、返回给上层的是什么？
本层的子树，是否是一颗平衡二叉树
3、本次递归中，要完成什么任务？
计算本层的高度差，并判断本层的左子树和右子树是否是一个平衡二叉树
4、代码实现
```java
/**
* 遍历左右子树的同时，计算左右子树的是否是个平衡二叉树
* @Param root
* @return
*/
public boolean isBalanced(TreeNode root) {
if (root == null){
return true;
}else {
//返回当前树的高度差是否小于等于1
return (Math.abs(maxHeight(root.left) - maxHeight(root.right)) <= 1)
//判断左子树和右子树，是否都是平衡的二叉树
&& isBalanced(root.left) && isBalanced(root.right) ;
}
}
//求树深度
int maxHeight(TreeNode root){
return root == null ? 0 : Math.max(maxHeight(root.left),maxHeight(root.right)) + 1;
}
```
本文参考lyl大佬的博客，发表自己的意见，感谢lyl大佬提供的思路！ yamika 发表于 2021-4-22 08:33
感觉递归最重要的还是找到终止条件，很多问题执行过程比较容易分析，递归终止条件需要推导一下
三个问题都重要哦，就像第三个例子，树的深度和是否平衡都要考虑进去，在返回信息的时候就要考虑这些。只考虑终止条件的话，不是很好变通 本帖最后由 Lokeyw 于 2021-4-22 00:07 编辑
感觉概念差不多会了，递归汉诺塔，我还是不会。就是用递归思想思考，感觉好难🤯 Lokeyw 发表于 2021-4-22 00:04
感觉概念差不多会了，递归汉诺塔，我还是不会。就是用递归思想思考，感觉好难🤯
同没搞清楚汉诺塔递归{:17_1089:} 感觉递归最重要的还是找到终止条件，很多问题执行过程比较容易分析，递归终止条件需要推导一下
页:
[1]