LeetCode 206. 反转链表题解，借用本题与关联题目，加强对递归的理解。

借着几道简单题，加强理解下递归。

递归

递归是一种编程技巧。

递归（英语：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

一种便于理解的心理模型，是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。

使用分治的思想，一个大问题我们可以拆分为n个小问题，其中n问题可由n-1的解获得。即后序答案由前序答案获得，同时递归有处理边界，总有一个前序的解是已知的。

任何使用递归实现的方法，都可以用非递归的方式（压栈）实现。

递归在程序中包含两个重要部分：

重复性、可叠加、最小化的动作【递推公式】；

边界条件，即函数是一定可返回、不爆栈的；

案例

排队获取队号

假设我们去做核酸排队，我们并不知道自己排在多少位。如何算出排位呢？

迭代：跳出队列，挨个数。
递归：问前面的人，前面的人再问前面的人，最后排在首位与工作人员接头的就是一号，将号码传回，依次叠加。

递归的做法相比迭代，我们自己的工作量少了很多，只需要在前序数字上+1。

递推公式

1

f(n)=f(n-1)+1

边界条件

1

n==1 【与核算人员接头了】

代码

1
2
3
4
5
6


public int getQueueNum(DoubleListNode node) {
    if (node.prev == null) {
        return 1;
    }
    return getQueueNum(node.prev) + 1;
}

计算斐波那契数列第n个值

在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

递推公式

1

F(n)=F(n - 1)+F(n - 2)

边界条件

1

F(0)=0，F(1)=1 【数列前两个值是已知的】

代码

1
2
3
4
5
6
7
8
9


public int fib(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}

小结

考虑问题的递归方案时，关键就在于分析：

递推公式；
边界条件；

同时跳转型数据结构很多问题，天然有被递归解决的特性，如链表、树结构。因为每一层、每个节点结构都是一致的，问题的解也是一致的，只是序列、前后项不同。

同时思考解时，只考虑相邻解的关系，不要被递归执行序绕晕。

优点	缺点
解决一些复杂问题时，编码很简洁	由于递归执行需要栈空间，会带来额外开销
无需多余的辅助变量、循环	可能造成`OOM`、栈溢出
可以用记录法、缓存降低复杂性、提高性能	不好的结构可能引发不必要的复杂性
非常适合处理跳转型、结构化的格式：树、图、`JSON`

题目

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 https://leetcode.cn/problems/reverse-linked-list/

分析

问题是：

反转链表；
返回反转后的链表头节点；

递归公式

我们先考虑问题1，尽可能缩小问题集。对应解设为f(node)，那么递推公式可以写为：

1

f(node)=node节点的下个节点的next指针指向node + f(node.next)

考虑递推公式时，我们可以假设f(node.next)的前序/后序问题已解决，只要有边界，递归解就一定执行的完。

边界条件

个人觉得有两个边界：

头节点反转时，需要设置head.next=null，因为后序节点的解不管这个，所以需要在头节点边界处理好；
调用到最后一个节点后，递归解停止执行；

代码

根据以上分析，可得代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


public static void reverseList(ListNode node) {
    // 边界2
    if (node == null || node.next == null) {
        return;
    }
    reverseList(node.next);
    // 下个的节点的next指向当前节点
    node.next.next = node;
    // 边界1
    node.next = null;
}

问题1已解，我们再考虑问题2：2. 返回反转后的链表头节点；，在边界2的返回处，我们将原先的末端节点返回，同时在递归调用f(node)的地方拿到此节点，递归序执行完毕后，将该结果返回给调用方。

代码微调即可：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


public static ListNode reverseList(ListNode node) {
    // 边界2
    if (node == null || node.next == null) {
        // 末端节点作为边界返回
        return node;
    }
    ListNode lastOne=reverseList(node.next);
    // 下个的节点的next指向当前节点
    node.next.next = node;
    // 边界1
    node.next = null;
    return lastOne;
}

相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

https://leetcode.cn/problems/same-tree/

分析

问题是：

判断树结构、值是否相同；

递归公式

如果是判断线性非跳转结构，比如数组，那我们的想法无法就是起两个指针，依次判断对应索引上值是不是一致即可。

类比一下，我们解设解为f(node1,node2)，那么递推公式可以写为：

1
2
3
4


// val判断值相等
// node1.left,node2.left node1.right,node2.right 判断保证结构一致
// 只要有一个判断为false，f解整体为false，因此每个递归调用间关系为且
f(node1,node2)=node1.val==node2.val + f(node1.left,node2.left) + f(node1.right,node2.right)

边界条件

两个边界：

当前节点值不同时，f(node1,node2)的解即为false；
调用到最后一个节点后，递归解停止执行；

代码

根据以上分析，可得代码：

1
2
3
4
5
6
7
8
9


public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null) {
        return q == null;
    }
    if (q == null) {
        return false;
    }
    return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

https://leetcode.cn/problems/subtree-of-another-tree/

分析

问题是：

判断后者是否为前者树🌲的子集；
1. 从某个节点开始，两棵树结构、值一致；

所以本题解有部分逻辑与【相同的树】一致。

递归公式

我们解设解为f(root,subRoot)，那么递推公式可以写为：

1
2
3
4


// isSameTree 判断树是否一致，参考上题分析
// node1.left,node2.left node1.right,node2.right 判断寻找下个可能满足sameTree的节点
// 只要有一个判断为true，f解整体为true，因此每个递归调用间关系为或
f(root,subRoot)=isSameTree(root,subRoot) + f(node1.left,node2.left) + f(node1.right,node2.right)

边界条件

两个边界：

isSameTree返回true，即root某个节点开始找到了与subRoot的子树时，解为true；
调用到最后一个节点后，递归解停止执行；

代码

根据以上分析，可得代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (root == null) {
        return subRoot == null;
    }
    return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null) {
        return q == null;
    }
    if (q == null) {
        return false;
    }
    return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

24. 两两交换链表中的节点

2022-10-11 新增

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

https://leetcode.cn/problems/swap-nodes-in-pairs/

分析

问题是：

链表节点两个为一组，两个节点互换位置（a/b两节点，a.next指向b.next，b.next指向原b（a.next），同时需维护组外的前序，即prev.next=b）；
1. 组内节点互换；
2. 组外维护新的首尾；
3. 一组两个节点称为一个pair；

递归公式

将对应解设为f(node)，那么递推公式可以写为：

1
2


// node.next.next 表示下一组的头
f(node)=node/node.next互换 + f(node.next.next)

同样，考虑递推公式时，我们需要假设f(node.next)的前序/后序问题已解决，只要有边界，递归解就一定执行的完。

边界条件

当下一组只有一个节点或者下一组没有节点时，我们的f()就执行完了；

代码

根据以上分析，可得代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


/**
* 返回当前链表被两两交换后的head头
* <p>
* 时间复杂度：整个过程完整遍历一次链表，O(n)
* 空间复杂度：递归有栈开销，O(n)
*/
public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    // 暂存head.next.next（用于反转下一段，并且返回给当前段用作segment.next）
    // 暂存head.next（用于返回新链表的头）
    ListNode third = head.next.next, second = head.next;
    head.next.next = head;
    head.next = swapPairs(third);
    return second;
}

递归#

案例#

排队获取队号#

递推公式#

边界条件#

代码#

计算斐波那契数列第n个值#

递推公式#

边界条件#

代码#

小结#

题目#

反转链表#

分析#

递归公式#

边界条件#

代码#

相同的树#

分析#

递归公式#

边界条件#

代码#

另一棵树的子树#

分析#

递归公式#

边界条件#

代码#

24. 两两交换链表中的节点#

分析#

递归公式#

边界条件#

代码#

递归

案例

排队获取队号

递推公式

边界条件

代码

计算斐波那契数列第n个值

递推公式

边界条件

代码

小结

题目

反转链表

分析

递归公式

边界条件

代码

相同的树

分析

递归公式

边界条件

代码

另一棵树的子树

分析

递归公式

边界条件

代码

24. 两两交换链表中的节点

分析

递归公式

边界条件

代码