专题一：递归算法_描述同一问题所用的算法-CSDN博客

本文链接：https://blog.csdn.net/AAlykk/article/details/144006453

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：了解什么是递归，并且掌握递归算法。

> 毒鸡汤：有些事情，总是不明白，所以我不会坚持。早安!

> 专栏选自：递归、搜索与回溯算法_დ旧言~的博客-CSDN博客

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

一、算法讲解

在解决⼀个规模为 n 的问题时，如果满足以下条件，我们可以使用递归来解决：

问题可以被划分为规模更小的子问题，并且这些子问题具有与原问题相同的解决方法。
当我们知道规模更小的子问题（规模为 n - 1）的解时，我们可以直接计算出规模为 n 的问题
的解。
存在⼀种简单情况，或者说当问题的规模足够小时，我们可以直接求解问题。

⼀般的递归求解过程如下：

验证是否满足简单情况。
假设较小规模的问题已经解决，解决当前问题。

上述步骤可以通过数学归纳法来证明。

二、算法习题

2.1 第一题

题目链接：汉诺塔问题 --- 力扣（LeetCode）

题目描述：

题目解析：

这里可以先康康如何移动盘子：汉诺塔移动

因为 A 中最后处理的是最大的盘子，所以在移动过程中不存在大盘子在小盘子上面的情况。则本题可以被解释为：

对于规模为 n 的问题，我们需要将 A 柱上的 n 个盘子移动到 C 柱上。
规模为 n 的问题可以被拆分为规模为 n-1 的子问题：
1. 将 A 柱上的上面 n-1 个盘子移动到B柱上。
2. 将 A 柱上的最大盘子移动到 C 柱上，然后将 B 柱上的 n-1 个盘子移动到C柱上。
当问题的规模变为 n=1 时，即只有⼀个盘子时，我们可以直接将其从 A 柱移动到 C 柱。

需要注意的是，步骤 2 中的 ① 考虑的是总体问题中的子问题 ② 情况。在处理子问题的子问题② 时，我们应该将 A 柱中的最上面的盘子移动到 C 柱，然后再将 B 柱上的盘子移动到 C 柱。在处理总体问题的子问题 b 时，A 柱中的最大盘子仍然是最上面的盘子，因此这种做法是通用的。

算法流程：

递归函数设计：void hanotaa(vector<int>& A, vector<int>& B, vector<int>& C, int n)

返回值：无；
参数：三个柱子上的盘子，当前需要处理的盘子个数（当前问题规模）。
函数作用：将 A 中的上面 n 个盘子挪到 C 中。

递归函数流程：

当前问题规模为 n=1 时，直接将 A 中的最上面盘子挪到 C 中并返回；
递归将 A 中最上面的 n-1 个盘子挪到 B 中；
将 A 中最上面的⼀个盘子挪到 C 中；
将 B 中上面 n-1 个盘子挪到 C 中。

代码呈现：

class Solution 
{
public:
    void hanota(vector<int>& a, vector<int>& b, vector<int>& c) 
    {
        dfs(a, b, c, a.size());
    }
    void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n) 
    {
        if (n == 1) 
        {
            c.push_back(a.back());
            a.pop_back();
            return;
        }
        dfs(a, c, b, n - 1);
        c.push_back(a.back());
        a.pop_back();
        dfs(b, a, c, n - 1);
   }
};

2.2 第二题

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

题目描述：

算法思路：

递归函数的含义：交给你两个链表的头结点，你帮我把它们合并起来，并且返回合并后的头结点。
函数体：选择两个头结点中较⼩的结点作为最终合并后的头结点，然后将剩下的链表交给递归函数去处理。
递归出⼝：当某⼀个链表为空的时候，返回另外⼀个链表。

函数头设计：Node* dfs( l1 , l2)

函数体的设计：

比较大小：l1->val <= l2->val
递归方法：l1->next = mergeTwoLists(l1->next, l2);
返回：l1;

递归出口：

if(l1 == nullptr) return l2;
if(l2 == nullptr) return l1;

代码呈现：

class Solution 
{
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        if (l1 == nullptr)
            return l2;
        if (l2 == nullptr)
            return l1;
        if (l1->val <= l2->val)
        {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else 
        {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

2.3 第三题

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

题目描述：

算法思路：

递归函数的含义：交给你⼀个链表的头指针，你帮我逆序之后，返回逆序后的头结点。
函数体：先把当前结点之后的链表逆序，逆序完之后，把当前结点添加到逆序后的链表后⾯即可。
递归出⼝：当前结点为空或者当前只有⼀个结点的时候，不⽤逆序，直接返回。

代码呈现：

class Solution 
{
public:
    ListNode* reverseList(ListNode* head) 
    {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

2.4 第四题

题目链接：24. 两两交换链表中的节点 - 力扣（LeetCode）

题目描述：

算法思路：

递归函数的含义：交给你⼀个链表，将这个链表两两交换⼀下，然后返回交换后的头结点。
函数体：先去处理⼀下第⼆个结点往后的链表，然后再把当前的两个结点交换⼀下，连接上后⾯处理后的链表。
递归出⼝：当前结点为空或者当前只有⼀个结点的时候，不⽤交换，直接返回。

代码呈现：

class Solution 
{
public:
    ListNode* swapPairs(ListNode* head) 
    {
        if (head == nullptr || head->next == nullptr)
            return head;
        auto tmp = swapPairs(head->next->next);
        auto ret = head->next;
        head->next->next = head;
        head->next = tmp;
        return ret;
    }
};

2.5 第五题

题目链接：50. Pow(x, n) - 力扣（LeetCode）

题目描述：

算法思路：

解法一：暴力循环（会超时）

解法二：快速幂

递归函数的含义：求出 x 的 n 次⽅是多少，然后返回。
函数体：先求出 x 的 n / 2 次⽅是多少，然后根据 n 的奇偶，得出 x 的 n 次⽅是多少。
递归出⼝：当 n 为 0 的时候，返回 1 即可。

函数头：

int pow(x , n)

函数体：

tmp = pow(x , n)
return n%2 == 0 ? tmp * tmp : tmp * tmp * x

递归出口：

n == 0 , return 1

细节问题：

n 有可能是负数（改成分数）
n 可能是 -2^31（采用 long long）

代码呈现：

class Solution 
{
public : 
    double myPow(double x, int n) 
    {
        return n < 0 ? 1.0 / pow(x, -(long long)n) : pow(x, n);
    }
    double pow(double x, long long n) 
    {
        if (n == 0)
            return 1.0;
        double tmp = pow(x, n / 2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }
};

2.6 第六题

题目链接：2331. 计算布尔二叉树的值 - 力扣（LeetCode）

题目描述：

算法思路：

1. 对于规模为 n 的问题，需要求得当前节点值。

2. 节点值不为 0 或 1 时，规模为 n 的问题可以被拆分为规模为 n-1 的⼦问题：

a. 所有⼦节点的值；
b. 通过⼦节点的值运算出当前节点值。

3. 当问题的规模变为 n=1 时，即叶⼦节点的值为 0 或 1，我们可以获取当前节点值为 0 或 1。

算法流程：

返回值：当前节点值；
参数：当前节点指针。
函数作⽤：求得当前节点通过逻辑运算符得出的值。

递归函数流程：

当前问题规模为 n=1 时，即叶⼦节点，直接返回当前节点值。
递归求得左右⼦节点的值。
通过判断当前节点的逻辑运算符，计算左右⼦节点值运算得出的结果。

代码呈现：

class Solution 
{
public:
    bool evaluateTree(TreeNode* root) 
    {
        if (root->left == nullptr)
            return root->val == 0 ? false : true;
        bool left = evaluateTree(root->left);
        bool right = evaluateTree(root->right);
        return root->val == 2 ? left | right : left & right;
    }
};

2.7 第七题

题目链接：129. 求根节点到叶节点数字之和 - 力扣（LeetCode）

题目描述：

算法思路：

在前序遍历的过程中，我们可以往左右⼦树传递信息，并且在回溯时得到左右⼦树的返回值。递归函数可以帮我们完成两件事：

将⽗节点的数字与当前节点的信息整合到⼀起，计算出当前节点的数字，然后传递到下⼀层进⾏递归。
当遇到叶⼦节点的时候，就不再向下传递信息，⽽是将整合的结果向上⼀直回溯到根节点。
在递归结束时，根节点需要返回的值也就被更新为了整棵树的数字和。

算法流程：

返回值：当前⼦树计算的结果（数字和）
参数 num：递归过程中往下传递的信息（⽗节点的数字）
函数作⽤：整合⽗节点的信息与当前节点的信息计算当前节点数字，并向下传递，在回溯时返回当前⼦树（当前节点作为⼦树根节点）数字和。

递归函数流程：

当遇到空节点的时候，说明这条路从根节点开始没有分⽀，返回 0；
结合⽗节点传下的信息以及当前节点的 val，计算出当前节点数字 sum；
如果当前结点是叶⼦节点，直接返回整合后的结果 sum；
如果当前结点不是叶⼦节点，将 sum 传到左右⼦树中去，得到左右⼦树中节点路径的数字和，然后相加后返回结果。

代码呈现：

class Solution {
public:
    int sumNumbers(TreeNode* root) { return dfs(root, 0); }
    
    int dfs(TreeNode* root, int presum) 
    {
        presum = presum * 10 + root->val;
        if (root->left == nullptr && root->right == nullptr)
            return presum;
        int ret = 0;
        if (root->left)
            ret += dfs(root->left, presum);
        if (root->right)
            ret += dfs(root->right, presum);
        return ret;
    }
};

2.8 第八题

题目链接：814. 二叉树剪枝 - 力扣（LeetCode）

题目描述：

算法流程：

如果我们选择从上往下删除，我们需要收集左右⼦树的信息，这可能导致代码编写相对困难。然⽽，通过观察我们可以发现，如果我们先删除最底部的叶⼦节点，然后再处理删除后的节点，最终的结果并不会受到影响。

因此，我们可以采⽤后序遍历的⽅式来解决这个问题。在后序遍历中，我们先处理左⼦树，然后处理⼦树，最后再处理当前节点。在处理当前节点时，我们可以判断其是否为叶⼦节点且其值是否为 0，如果满⾜条件，我们可以删除当前节点。

需要注意的是，在删除叶⼦节点时，其⽗节点很可能会成为新的叶⼦节点。因此，在处理完⼦节点后，我们仍然需要处理当前节点。这也是为什么选择后序遍历的原因（后序遍历⾸先遍历到的⼀定是叶⼦节点）。
通过使⽤后序遍历，我们可以逐步删除叶⼦节点，并且保证删除后的节点仍然满⾜删除操作的要求。这样，我们可以较为⽅便地实现删除操作，⽽不会影响最终的结果。
若在处理结束后所有叶⼦节点的值均为 1，则所有⼦树均包含 1，此时可以返回。

算法流程：

返回值：⽆；
参数：当前需要处理的节点；
函数作⽤：判断当前节点是否需要删除，若需要删除，则删除当前节点。

后序遍历的主要流程：

1.递归出⼝：当传⼊节点为空时，不做任何处理；
2. 递归处理左⼦树；
3. 递归处理右⼦树；
4. 处理当前节点：判断该节点是否为叶⼦节点（即左右⼦节点均被删除，当前节点成为叶⼦节点），并且节点的值为 0：

如果是，就删除掉；
如果不是，就不做任何处理。

代码呈现：

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) 
    {
        if (!root) 
            return nullptr;

        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        
        if (!root->left && !root->right && !root->val)
            return nullptr;
            
        return root;
    }   
};