LeetCode 刷题 -- 递归

如果函数中存在调用自身的情况，这种就叫做递归。

递归本质的思想就是将大问题分解成小问题，小问题分解成更小的问题，直到这个问题可以直接计算出来。如何应用递归呢？要思考以下几个问题：

1、f(n)和 f(n-1) 有什么关联？--->寻找递归关系

2、f(1)、f(2)。。这种简单的能不能直接计算出结果？ --->寻找递归边界

例题： 

509、斐波那契数

问题描述

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

分析：递归调用的方法题目已经给出来了，直接写代码即可。

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

70、爬楼梯

问题描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

分析：（这个和斐波那契数还是很相似的）

当n=1的时候，有1种方法

当n=2的时候，有2种方法 ： 1+1或者2

当n=n的时候，有几种方法呢？如果最后一步走1个台阶，那么就是n=n-1时候的方法，如果最后一步走2个台阶，那么就是n=n-2的方法，因此 f(n)=f(n-1)+f(n-2)

因此代码可以写成如下：

public class climbStairs {

    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        } else {
            return climbStairs(n-1) + climbStairs(n-2);
        }
    }
}

// 但是很遗憾，LeetCode运行超时了

优化：

在上述代码的递归调用里，调用的是f(n-1)和f(n-2)，但是在f(n-1)的递归里面，f(n-2)其实已经计算过了，但是后面还会重复计算。借用如下网图进行理解：计算f8的时候，f6计算了两次，f5计算了三次。。。

因此可以采用“记忆递归”的方法，定义一个数据，下标就对应着对应的次数，每次计算完就把计算结果存入，如果没有值就去计算，如果有值就直接获取。

public class climbStairs{
    public int climbStairs(int n) {
        // memory数组记录对应下标数字，登上台阶的方法。
        int[] memory = new int[n + 1];
        return climbStairs(n, memory);
    }
    
    private int climbStairs(int n, int[] memory) {
        if (memory[n]>0) {
            return memory[n];
        }
        if (n == 1) {
            memory[n] = 1;
        } else if (n == 2) {
            memory[n] = 2;
        } else {
            memory[n] = climbStairs(n-1, memory) + climbStairs(n-2, memory);
        }
        return memory[n];
    }
}

​​​​​​226. 翻转二叉树

问题描述

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。（看图其实就是直接镜像翻转。）

分析：

从根节点出发，如果这个节点存在子节点，则左右子节点对换位置（左节点变成右节点，右节点变成左节点。）同时，这个节点的子节点也要进行相同的操作。

注意空指针的情况：

1、如果节点本身为null，则不用操作，跳出递归

2、如果节点的左右子节点全为null，也不需要操作，可以跳出递归

3、如果只有一个节点为null，这种是需要调换左右节点的，假设左节点不为null，右节点为null，那么调换之后，左节点为null，右节点不为null，因此可以不需要特殊处理。

按照上述思路的代码：

public class invertTree{
    public TreeNode invertTree(TreeNode root) {
        invertNode(root);
        return root;
    }
    
    private void invertNode(TreeNode node) {
        // 节点本身为null，跳出递归
        if (node == null) {
            return;
        }
        // 节点没有子节点，跳出递归
        if (node.left == null && node.right == null) {
            return;
        }
        // 获取左右节点，交换顺序，子节点进入递归
        TreeNode left = node.left;
        TreeNode right = node.right;
        node.left = right;
        node.right = left;
        invertNode(right);
        invertNode(left);
    }
}

优化代码结构

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.right = left;
        root.left = right;
        return root;
    }
}

112. 路径总和

题目描述

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

分析：

树形的结构一般都是采用递归的方式去做，本题是寻找有没有从root根节点到叶子节点路径之和等于sum的路径。

1、第一步简化：寻找root.left或者root.right 到叶子节点路径之和等于sum-root.value的路径。

2、理解了第一步的简化思想，这道题基本上就迎刃而解了

3、细节问题：递归的边界在哪里？一直到叶子节点（即没有左右节点），如果叶子节点的值等于一步步减去父节点剩下的值，则代表有该路径，否则就是没有该路径。

代码

public class hasPathSum{
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        // 代表当前节点为叶子节点
        if (root.right == null && root.left == null) {
            return targetSum == root.val;
        }
        int remain = targetSum - root.val;
        // 只有有一条存在，就返回true
        return hasPathSum(root.right, remain) || hasPathSum(root.left, remain);
    }
}

优化：

1、在爬楼梯的题目中，简单的递归调用导致超时无法通过，因此“用空间换时间”做了优化：即每次计算的值先存储下来，如果后续在递归调用中还会遇到计算这个值的情景下，就可以跳过计算，直接返回事先存储的值。这是一种优化思路。

2、在查看题解的过程中，发现另外一种优化思路：即反向看待问题。还是70题爬楼梯为例：

f(n)=f(n-1)+f(n-2)那么反向看可以知道：

f(3)=f(2)+f(1)

f(4)=f(3)+f(2)

....

代码如下：

int[] ints = new int[n + 1];
ints[0] = 0;
ints[1] = 1;
ints[2] = 2;
for (int i = 3; i <= n; i++) {
    ints[i] = ints[i - 1] + ints[i - 2];
}