三步走套路递归问题

Leetcode 递归

算法

发布日期: 2023-09-04

更新日期: 2023-09-24

文章字数: 1.2k

阅读时长: 4 分

阅读次数:

三步走套路递归问题

写递归的题目的时候发现总是不清楚递归的次序和条件，当前的函数做了什么？它调用自身后的下一层又做了什么…这样想还是比较复杂的，思考了很久，在网上学习八股的知识的时候想到了具体的过程，下面就来说说看。

1. 三步走套路

先上一张图片，里面清晰地记录了递归的过程和每一层所需要实现的作用。
个人理解：递归，其实就是将一级递归（也就是最开始的那层递归），调用之后需要返回特定的值，一直递归直到找到终止条件。
由此可见
1. 找整个递归的终止条件：递归应该在什么时候结束？
2. 找返回值：应该给上一级返回什么信息？
3. 本级递归应该做什么：在这一级递归中，应该完成什么任务？

2. 举例实战

Leetcode 24. 两两交换链表中的节点
简单利用三部曲：1. 找到终止条件（也就是特例情况）；2. 找到前一个递归级的返回值；3.在当前的递归中需要什么（具体分析）

开始实际操作！

2.1 题目说明

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

2.2 套路分析

找终止条件。 什么情况下递归终止？没得交换的时候，递归就终止了，因此当链表只剩一个节点或者没有节点的时候，自然递归就终止了。
找返回值。 我们希望向上一级递归返回什么信息？由于我们的目的是两两交换链表中相邻的节点，因此自然希望交换给上一级递归的是已经完成交换处理，即已经处理好的链表。
本级递归应该做什么。 结合第二步，看下图！由于只考虑本级递归，所以这个链表在我们眼里其实也就三个节点：head、head.next、已处理完的链表部分。而本级递归的任务也就是交换这3个节点中的前两个节点。

2.3 代码实现

具体的代码如下(java)：

class Solution {
    public ListNode swapPairs(ListNode head) {
      	//终止条件：链表只剩一个节点或者没节点了，无法再次进行交换。返回的是已经处理好的链表
        if(head == null || head.next == null){
            return head;
        }
      	//一共三个节点:head, next, swapPairs(next.next)
      	//下面的任务便是交换这3个节点中的前两个节点
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
      	//根据第二步：返回给上一级的是当前已经完成交换后，即处理好了的链表部分，需要返回的值
        return next;
    }
}

3.相似题目分析

Leetcode 226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：
```
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
```
分析：
- 终止条件：无法返回根节点root,也就是根节点此时为空null
- 找上一回递归的返回值：对于每次的翻转，我们希望返回的是对应枝节的根节点root，这里先不用考虑每一层的操作，反正最后返回的是该层的根节点
- 本级递归的操作：每一层都会进行左右交换，首先确定左子树，接着将左子树的每个子节点依次进行递归左右交换操作，实现每一层的交换，递归从底到顶返回的时候再将原始的左子树和右子树进行交换即可。也就是要求使用两次递归，一次是左右子树之间的交换，一次是根左右子树之间的交换，最后返回上一级的递归结果

代码：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return root;//终止
        }
        TreeNode leftafter=root.left;
        root.left=invertTree(root.right);
        root.right=invertTree(leftafter);
        
        return root;//前一次的返回值
    }
}