递归、搜索与回溯（一）——前言和旧题新做

🕗 发布于 2024-10-19 16:30 深度优先算法

文章目录

重新理解递归
后续名词解释
旧题重做（以递归）
- 合并两个有序链表
- 反转链表

重新理解递归

简单来说，递归就是方法自己调用自己，我们已经了解。这里讨论：

为什么用递归？

直接说结论：主问题能够分出相同的子问题，而这个子问题又能分出相同的子问题，这里的相同指的是解决方法相同

以二叉树的后序遍历为例，对整个二叉树进行遍历就是主问题，我们已经学过做法，这时候要先遍历根结点的左子树，那么此时子问题出现了：对根结点的左子树进行后序遍历；对此树遍历，还是要先对它的左子树进行遍历，这又是再次分出的一个子问题。主问题和子问题的解决方法也都是一致的，即左右中。
如何理解递归并写好一个递归？

新的思想：宏观看待递归的过程：
- 不要太在意递归的细节展开图，即不必在意递归的细节，否则容易将自己绕晕。
- 将递归方法看作一个工具，相信递归可以做到某个任务，在此基础上进行递归代码的编写
写递归的步骤：
- 找到相同的子问题，完成方法头的设计，即方法返回值，参数列表
- 只关心某一个子问题是如何解决的，完成关键方法体的编写
- 注意递归的出口，即不可分割的子问题，避免写出死递归
以二叉树后序遍历并打印为例：
- 确定子问题：对以某个结点为根结点的二叉树进行后序遍历并打印
  
  此时不难完成方法头的设计：void postOrder(TreeNode root)
- 只关心某个子问题是如何解决的，相信递归方法可以完成该任务：首先得遍历它的左子树，再右子树，最后打印自己结点的值。
  
  此时完成关键方法体：
```
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val);
```
- 找到递归的出口，当某棵树为空，此时不能再分割出子问题。
  
  完成递归出口：
```
if(root == null) return;
```
对于迭代（循环）和递归问题，其实都是解决重复子问题，如何选择？

首先递归展开图其实就是一棵树，对于树结构简单的问题，一般采用迭代（递归）的方式；对于树结构复杂的问题，一般采用递归的方式。

后续名词解释

这里的名词有：搜索、深度优先遍历、深度优先搜索、宽度优先遍历、宽度优先搜索、暴搜、回溯与剪枝

深度和宽度的区别，二叉树和图论部分已经见识过了。

遍历与搜索的区别：遍历是形式，目的是搜索，但其实可以认为是同一种东西。

搜索和暴搜其实可以理解为同一件事情，都是在解空间内暴力枚举所有的情况。

搜索可分为深度优先搜索（DFS）和宽度优先搜索（BFS）。

回溯问题本质上就是深度优先搜索问题，即当尝试某种情况时发现行不通返回上一级。而剪枝就是在搜索过程中去除不可能的分支。

另外，跳出一种局限思维，说到深度优先搜索或者搜索问题，不能只想到二叉树和图论问题，想想某个问题的所有情况是不是树状或者图状结构。例如，全排列问题，这类问题可以通过画树状图的方法解决，每一步选择不同的数字都会产生不同的结果，这个树状图其实就是一棵决策树。所以，如果可以针对某个问题画出决策树，那么该问题就可以利用搜索的方式解决

将递归、搜索和回溯放在一起的原因：回溯本质上是深搜，深搜用递归解决。 学习时，按照递归、深搜、回溯的顺序进行。

旧题重做（以递归）

合并两个有序链表

原题链接：21. 合并两个有序链表 - 力扣（LeetCode）

在这里插入图片描述

重复子问题：

思路：给我们两个链表的头，我们第一步一定是比较这两个头的值的大小，如上图示例1，1和1相等，认为哪个“小”都可以，假设认为第一个链表的1小，判断完毕后，此时问题就转化为合并链表 2->4 和链表 1->3->4，大问题此时就转化为一个小问题。重复子问题就是合并两个链表（两个链表的大小越来越小）
子问题如何解决？

判断此时两个链表头的值的大小，然后拼接后序子问题合并的链表。
递归出口：

某一个链表为null，返回另一个即可

【代码实现】

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //begin
        if(list1 == null) {
            return list2;
        }
        if(list2 == null) {
            return list1;
        }
        
        if(list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        } 
        //end
    }
}

反转链表

原题链接：206. 反转链表 - 力扣（LeetCode）

在这里插入图片描述

以示例1的图为例：

寻找重复子问题：

（从头开始反转） 要将整个链表反转，可以先将结点1和结点2反转，即结点2的next指针指向结点1，此时完成了1->2链表的反转，但是由于修改了结点2的next指针，所以结点3找不到了，所以这种子问题的寻找不合理。

（从尾开始反转） 这种方式避免了指针丢失的问题，例如，先将结点1后面的链表反转，再将结点1加入到反转链表中。

因此，给我们原链表头指针，我们不能直接反转，要先走到末尾，然后依次往前反转。将链表视为一棵树来思考，这个过程就类似于后序遍历。
子问题如何解决？

针对某次调用，我们只有head参数，想做到反转，就得让head.next的next指针指向head，此时就完成了反转。

先不考虑函数的出口，看整个链表：结点4和结点5反转、3和4反转、2和3反转、1和2反转。此时出现了一个问题，最后一次1和2反转做的是让2指向1，但是结束后1应该指向null，解决方案是：每次反转后，将本次调用的head的next置为null，这样就能保证最后结点1能够指向null。

要求返回反转后的链表的头，也就是结点5，我们可以将这个值作为返回值一直传递。
递归出口

最后一个结点5就是最终的返回值，所以我们希望“后序遍历”时到达结点5就停下，并将这个值不断返回，结点5（尾结点）的特点就是它的next指针为null。

除此之外，如果一开始给的原链表的头就是null，即空链表，直接返回即可。