递归思想刷题总结

2023-05-16

核心思想

我们在调用递归函数的时候，把递归函数当做普通函数（黑箱）来调用，即明白该函数的输入输出是什么，而不用管此函数内部在做什么。（千万不要跳进去了，你脑袋能压几个栈呀？）

递归算法的关键要明确函数的定义，相信这个定义，而不要跳进递归细节。
写二叉树的算法题，都是基于递归框架的，我们先要搞清楚 root 节点它自己要做什么，然后根据题目要求选择使用前序，中序，后续的递归框架。
二叉树题目的难点在于如何通过题目的要求思考出每一个节点需要做什么，这个只能通过多刷题进行练习了。

上述参考训练递归思维–手把手带你刷二叉树（第一期）
上述参考训练递归思维–手把手带你刷二叉树（第二期），还有部分在公众号续
上述参考训练递归思维–手把手带你刷二叉树（第三期），还有部分在公众号续

例题

【力扣-395. 至少有K个重复字符的最长子串】
解题思路
本题要求的一个最长的子字符串的长度，该子字符串中每个字符出现的次数都最少为 kk。
求最长子字符串/区间的这类题一般可以用滑动窗口来做，但是本题滑动窗口的代码不好写，我改用递归。也借本题来帮助大家理解递归。
重点：我们在调用递归函数的时候，把递归函数当做普通函数（黑箱）来调用，即明白该函数的输入输出是什么，而不用管此函数内部在做什么。

下面是详细讲解。

递归最基本的是记住递归函数的含义（务必牢记函数定义）：本题的 longestSubstring(s, k)函数表示的就是题意，即求一个最长的子字符串的长度，该子字符串中每个字符出现的次数都最少为 kk。函数入参 ss 是表示源字符串；kk 是限制条件，即子字符串中每个字符最少出现的次数；函数返回结果是满足题意的最长子字符串长度。
递归的终止条件（能直接写出的最简单 case）：如果字符串 ss 的长度少于 kk，那么一定不存在满足题意的子字符串，返回 0；
调用递归（重点）：如果一个字符 cc 在 ss 中出现的次数少于 kk 次，那么 ss 中所有的包含 cc 的子字符串都不能满足题意。所以，应该在 ss 的所有不包含 cc 的子字符串中继续寻找结果：把 ss 按照 cc 分割（分割后每个子串都不包含 cc），得到很多子字符串 tt；下一步要求 tt 作为源字符串的时候，它的最长的满足题意的子字符串长度（到现在为止，我们把大问题分割为了小问题(ss → tt)）。此时我们发现，恰好已经定义了函数longestSubstring(s, k)就是来解决这个问题的！所以直接把 longestSubstring(s, k) 函数拿来用，于是形成了递归。
未进入递归时的返回结果：如果 ss 中的每个字符出现的次数都大于 kk 次，那么 ss 就是我们要求的字符串，直接返回该字符串的长度。

总之，通过上面的分析，我们看出了：我们不是为了递归而递归。而是因为我们把大问题拆解成了小问题，恰好有函数可以解决小问题，所以直接用这个函数。由于这个函数正好是本身，所以我们把此现象叫做递归。小问题是原因，递归是结果。而递归函数到底怎么一层层展开与终止的，不要用大脑去想，这是计算机干的事。我们只用把递归函数当做一个能解决问题的黑箱就够了，把更多的注意力放在拆解子问题、递归终止条件、递归函数的正确性上来。

class Solution {
    public int longestSubstring(String s, int k) {
        if (s.length() < k) return 0;
        HashMap<Character, Integer> counter = new HashMap();
        for (int i = 0; i < s.length(); i++) {
            counter.put(s.charAt(i), counter.getOrDefault(s.charAt(i), 0) + 1);
        }
        for (char c : counter.keySet()) {
            if (counter.get(c) < k) {
                int res = 0;
                for (String t : s.split(String.valueOf(c))) {
                    res = Math.max(res, longestSubstring(t, k));
                }
                return res;
            }
        }
        return s.length();
    }
}

以上摘抄自负雪明烛的算法题解

【力扣-654. 最大二叉树】

class Solution {
    /* 主函数 */
    TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    /* 将 nums[lo..hi] 构造成符合条件的树，返回根节点 */
    TreeNode build(int[] nums, int lo, int hi) {
        // base case
        if (lo > hi) {
            return null;
        }

        // 找到数组中的最大值和对应的索引
        int index = -1, maxVal = Integer.MIN_VALUE;
        for (int i = lo; i <= hi; i++) {
            if (maxVal < nums[i]) {
                index = i;
                maxVal = nums[i];
            }
        }

        TreeNode root = new TreeNode(maxVal);
        // 递归调用构造左右子树
        root.left = build(nums, lo, index - 1);
        root.right = build(nums, index + 1, hi);

        return root;
    }
}

总结：
我写的代码如下，思路与上面的示例代码是一样的，但是由于频繁的创建数组，导致时间复杂度、空间复杂度均比示例代码高。我的代码击败了5%的Java用户，而示例代码击败了99%的Java用户 ::>_<:: 。由此可见，辅助函数的作用之大。

class Solution {
    // 给定不含重复数组的整数数组nums，返回构建最大二叉树
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        
        int index = 0;
        int max = Integer.MIN_VALUE;
        for (int i=0; i<nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
                index = i;
            }
        }
        TreeNode node = new TreeNode(max);
        if (nums == null || nums.length == 0) {
            return null;
        }
        int[] nums1 = new int[index];
        int[] nums2 = new int[nums.length - index - 1];
        for (int i = 0; i < nums1.length; i++) {
            nums1[i] = nums[i];
        }
        for (int i = 0; i < nums2.length; i++) {
            nums2[i] = nums[index + i + 1];
        }
        node.left = constructMaximumBinaryTree(nums1);
        node.right = constructMaximumBinaryTree(nums2);
        return node;
    }
}

【力扣-105. 从前序与中序遍历序列构造二叉树】

/* 主函数 */
TreeNode buildTree(int[] preorder, int[] inorder) {
    return build(preorder, 0, preorder.length - 1,
                 inorder, 0, inorder.length - 1);
}

/* 
   若前序遍历数组为 preorder[preStart..preEnd]，
   后续遍历数组为 postorder[postStart..postEnd]，
   构造二叉树，返回该二叉树的根节点 
*/
TreeNode build(int[] preorder, int preStart, int preEnd, 
               int[] inorder, int inStart, int inEnd) {

    if (preStart > preEnd) {
        return null;
    }

    // root 节点对应的值就是前序遍历数组的第一个元素
    int rootVal = preorder[preStart];
    // rootVal 在中序遍历数组中的索引
    int index = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == rootVal) {
            index = i;
            break;
        }
    }

    int leftSize = index - inStart;

    // 先构造出当前根节点
    TreeNode root = new TreeNode(rootVal);
    // 递归构造左右子树
    root.left = build(preorder, preStart + 1, preStart + leftSize,
                      inorder, inStart, index - 1);

    root.right = build(preorder, preStart + leftSize + 1, preEnd,
                       inorder, index + 1, inEnd);
    return root;
}

总结：
这个题和力扣-106. 从中序与后序遍历序列构造二叉树一样，是经典题了。我觉得主要的难点在于：

如何能够想到调用辅助方法TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd)，需要考虑形参为什么这么设置？
递归构造左右子树时，细节的边界问题，一不留神，就会报错Memory Limit Exceeded。根据经验来说，对于中序遍历，可以利用index确定边界，然而对于前序遍历，需要计算一下左子树的长度，借助这个来表示。这儿很关键，很容易出错！

	int leftSize = index - inStart;
    
    // 递归构造左右子树
    root.left = build(preorder, preStart + 1, preStart + leftSize,
                      inorder, inStart, index - 1);

    root.right = build(preorder, preStart + leftSize + 1, preEnd,
                       inorder, index + 1, inEnd);

【力扣-652. 寻找重复的子树】

// 记录所有子树以及出现的次数
HashMap<String, Integer> memo = new HashMap<>();
// 记录重复的子树根节点
LinkedList<TreeNode> res = new LinkedList<>();

/* 主函数 */
List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    traverse(root);
    return res;
}

/* 辅助函数 */
String traverse(TreeNode root) {
    if (root == null) {
        return "#";
    }

    String left = traverse(root.left);
    String right = traverse(root.right);

    String subTree = left + "," + right+ "," + root.val;

    int freq = memo.getOrDefault(subTree, 0);
    // 多次重复也只会被加入结果集一次
    if (freq == 1) {
        res.add(root);
    }
    // 给子树对应的出现次数加一
    memo.put(subTree, freq + 1);
    return subTree;
}

总结：
如果你想知道以自己为根的子树是不是重复的，是否应该被加入结果列表中，你需要知道什么信息？
你需要知道以下两点：
1、以我为根的这棵二叉树（子树）长啥样？
2、以其他节点为根的子树都长啥样？

第一点可以通过拼接字符串的方式序列化二叉树，这样就可以描述二叉树的结构；第二点可以通过引入哈希表，让每个节点把序列化结果存进去，这样对于每个节点，就可以知道有没有其他的子树和自己重复了。

【力扣-538. 把二叉搜索树转换为累加树】

/**
 * 神了，这算法还是利用BST的中序遍历是升序这一性质
 * 只不过稍微变换了一下，变成了降序
 */
class Solution {
    private int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        return inorder(root);
    }

    private TreeNode inorder(TreeNode root) {
        if (root == null) {
            return null;
        }
        inorder(root.right);
        sum += root.val;
        root.val = sum;
        inorder(root.left);
        return root;
    }
}

总结：
这道题的核心还是 BST 的中序遍历特性，只不过我们修改了递归顺序，降序遍历 BST 的元素值，从而契合题目累加树的要求。

简单总结下吧，BST 相关的问题，要么利用 BST 左小右大的特性提升算法效率，要么利用中序遍历的特性满足题目的要求，就这。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)