面试算法高频03-递归

认识递归

1. 递归的概念与特性：递归本质类似循环，是通过函数体进行的循环操作。借助电影《盗梦空间》类比，递归如同主角在不同梦境层穿梭，向下进入不同递归层，向上能回到原来一层，每一层环境和周围元素相似，主角在不同层级梦境中会发生变化并携带变化。
2. 递归的实现——计算n!：计算n的阶乘（n!=1×2×3×…×n）是递归的经典示例。定义Factorial(n)函数，当n <= 1时返回1，否则返回n * Factorial(n - 1) 。以factorial(6)为例，详细展示了递归计算过程。
3. 递归代码模板
   • Python代码模版：recursion(level, param1, param2, ...)函数结构为：先设置递归终止条件（if level > MAX_LEVEL），接着处理当前层逻辑（process(level, data...)），然后向下递归（self.recursion(level + 1, p1, ...)），最后根据需要恢复当前层状态。
   • Java代码模版：public void recur(int level, int param)方法同样包含递归终止条件（if (level > MAX_LEVEL)）、当前逻辑处理（process(level, param)）、向下递归（recur(level: level + 1, newParam)）和恢复当前状态（restore current status）这些关键部分。
4. 递归的思维要点
   • 摒弃人肉递归：避免手动模拟递归过程，这是理解递归的最大误区，应直接依据函数定义编写代码。
   • 分解问题：找到最近最简方法，将问题拆解成可重复解决的子问题，利用重复子问题简化求解。
   • 运用数学归纳法思维：类似点燃炮竹，保证基础情况（第一个炮竹能点燃）成立，假设某一情况（前一个炮竹能点燃）成立时能推出下一个情况（下一个炮竹能点燃）成立，以此构建递归逻辑。

习题

题目描述

给定一个正整数 (n) ，计算 (n) 的阶乘 (n!) ，其中 (n! = 1\times2\times3\times\cdots\times n) ，需用Python语言编写函数实现该计算。

最优解（即图中代码所示方法）

def Factorial(n):if n <= 1:return 1return n * Factorial(n - 1)

解析

• 递归终止条件： if n <= 1: return 1 这部分是递归的关键终止条件。因为 (0!) 和 (1!) 的值都为 (1) ，当函数参数 (n) 为 (0) 或者 (1) 时，直接返回 (1) ，不再继续递归调用，避免无限循环。
• 递归调用： return n * Factorial(n - 1) 体现了阶乘计算的核心逻辑。根据阶乘的定义，(n!) 等于 (n) 乘以 ((n - 1)!) ，所以函数在 (n > 1) 时，通过不断调用自身并将参数减 (1) ，逐步计算出最终结果。比如计算 (5!) ，函数会依次计算 (5\times4!) ， (4!) 又会计算为 (4\times3!) ，以此类推，直到遇到终止条件 (1!) 返回 (1) ，再逐步回代计算出最终结果。 这种递归实现简洁且准确地表达了阶乘的计算逻辑。

题目复述

爬楼梯（Climbing Stairs） ：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？（来源：力扣 https://leetcode-cn.com/problems/climbing-stairs/ ）

最优解（递归实现思路，实际中更优解一般是迭代等方式 ）

def climbStairs(n):if n == 1:return 1if n == 2:return 2return climbStairs(n - 1) + climbStairs(n - 2)

分析

• 递归终止条件：当 n == 1 时，只有一种爬法，即一次爬一阶，所以返回 1 ；当 n == 2 时 ，可以一次爬两阶，或者分两次每次爬一阶，共两种爬法，返回 2 。这两个条件是递归结束的标志，避免无限递归。
• 递归调用逻辑：对于 n > 2 的情况，到达第 n 阶楼梯的方法数，等于到达第 n - 1 阶楼梯的方法数加上到达第 n - 2 阶楼梯的方法数。因为到达第 n 阶楼梯，要么是从第 n - 1 阶再爬一阶上来的，要么是从第 n - 2 阶一次爬两阶上来的。所以通过 return climbStairs(n - 1) + climbStairs(n - 2) 进行递归调用，不断将问题规模缩小，直到满足终止条件。

不过需要注意，纯递归实现会存在大量重复计算，时间复杂度较高（指数级） 。实际应用中，更推荐使用迭代法（如动态规划的迭代实现） 、矩阵快速幂等优化方法来降低时间复杂度。

题目描述

爬楼梯问题拓展

假设你正在爬楼梯，需要 n 阶才能到达楼顶，每次你可以爬 1 个、2 个或 3 个台阶 ，求爬到楼顶有多少种不同的方法。

递归实现代码

代码展示

def climbStairs(n):if n == 1:return 1elif n == 2:return 2elif n == 3:return 4return climbStairs(n - 1) + climbStairs(n - 2) + climbStairs(n - 3)

代码解析

递归终止条件

• 当 n == 1 时 ，只有一种爬法，即一次爬一阶，所以返回 1 。
• 当 n == 2 时，有两种爬法：一次爬两阶 ，或者分两次每次爬一阶，返回 2 。
• 当 n == 3 时，有四种爬法：（1, 1, 1） 、（1, 2）、（2, 1）、（3） ，返回 4 。这些条件是递归结束的标志，避免无限递归。

递归调用逻辑

对于 n > 3 的情况，到达第 n 阶楼梯的方法数，等于到达第 n - 1 阶楼梯的方法数、到达第 n - 2 阶楼梯的方法数与到达第 n - 3 阶楼梯的方法数之和 。因为到达第 n 阶楼梯，要么是从第 n - 1 阶再爬一阶上来的，要么是从第 n - 2 阶爬两阶上来的，要么是从第 n - 3 阶爬三阶上来的 。所以通过 return climbStairs(n - 1) + climbStairs(n - 2) + climbStairs(n - 3) 进行递归调用，不断将问题规模缩小，直到满足终止条件。

复杂度分析

时间复杂度

由于存在大量重复计算，时间复杂度为指数级，约为 (O(3^n)) ，随着 n 的增大，计算量会急剧增加。

空间复杂度

主要取决于递归调用栈的深度，在最坏情况下为 (O(n)) 。

优化思路

动态规划优化

这种纯递归实现效率较低，存在大量重复计算。可采用动态规划（如使用数组记录中间结果避免重复计算） 、矩阵快速幂等方法优化，将时间复杂度降低。 例如动态规划的迭代实现：

def climbStairs(n):if n == 1:return 1elif n == 2:return 2elif n == 3:return 4dp = [0] * ndp[0], dp[1], dp[2] = 1, 2, 4for i in range(3, n):dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]return dp[-1]

此方法用数组 dp 记录爬到第 i 阶的方法数，通过迭代计算，避免了重复计算，时间复杂度降为 (O(n)) ，空间复杂度也为 (O(n)) ，还可进一步优化空间复杂度。

题目描述

给定一个二叉树的根节点 root，判断该二叉树是否为有效的二叉搜索树。在二叉搜索树中，对于任意节点，其左子树中所有节点的值均小于该节点的值，右子树中所有节点的值均大于该节点的值，并且左右子树也都必须是二叉搜索树。

最优解（Python 代码）

# 定义二叉树节点类
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def __init__(self):self.prev = float('-inf')  # 记录中序遍历的前一个节点值，初始化为负无穷def isValidBST(self, root):if not root:return True# 递归检查左子树if not self.isValidBST(root.left):return False# 检查当前节点与前一个节点值的关系if root.val <= self.prev:return Falseself.prev = root.val# 递归检查右子树return self.isValidBST(root.right)

解析

1. 数据结构定义：首先定义了 TreeNode 类来表示二叉树的节点，每个节点包含一个值 val ，以及指向左子节点 left 和右子节点 right 的指针。这是构建二叉树和进行后续操作的基础。
2. 类初始化：在 Solution 类的 __init__ 方法中，初始化了一个变量 prev ，并将其值设为负无穷 float('-inf') 。这个变量用于记录在中序遍历过程中前一个节点的值，以便在遍历过程中比较当前节点值与前一个节点值的大小关系，从而判断是否符合二叉搜索树的规则。
3. 递归函数主体：
   • 递归终止条件：当 root 为空节点时，即 not root 条件成立，直接返回 True 。因为空树被定义为有效的二叉搜索树，不存在违反规则的情况。
   • 中序遍历递归检查左子树：通过 self.isValidBST(root.left) 递归调用自身来检查左子树是否为有效的二叉搜索树。如果左子树不是有效的二叉搜索树，直接返回 False ，无需继续检查当前节点和右子树。这是因为只要二叉树的任何一部分不符合规则，整个二叉树就不是有效的二叉搜索树。
   • 检查当前节点：在左子树检查通过后，比较当前节点的值 root.val 和记录的前一个节点的值 self.prev 。如果 root.val <= self.prev ，说明违反了二叉搜索树中序遍历结果应是升序序列的规则（即当前节点值应大于前一个节点值），返回 False 。如果当前节点值符合规则，则更新 self.prev 为当前节点的值 root.val ，为后续检查右子树做准备。
   • 中序遍历递归检查右子树：通过 self.isValidBST(root.right) 递归调用自身来检查右子树是否为有效的二叉搜索树。如果右子树检查通过，说明整个二叉树是有效的二叉搜索树，返回 True ；如果右子树检查不通过，则返回 False 。

算法复杂度

• 时间复杂度：该算法需要对二叉树的每个节点进行一次访问，所以时间复杂度为 (O(n)) ，其中 (n) 是二叉树的节点数。
• 空间复杂度：在递归过程中，递归调用栈的深度最大为二叉树的高度 (h) 。在最坏情况下（二叉树为单链表形式），高度 (h = n) ，此时空间复杂度为 (O(n)) ；在最好情况下（二叉树为完全平衡树），高度 (h = \log n) ，空间复杂度为 (O(\log n)) 。

题目描述（翻转二叉树 - Invert Binary Tree ）

给定一棵二叉树的根节点 root ，需要将这棵二叉树进行翻转，也就是交换每个节点的左右子树。例如，对于二叉树 root = [4,2,7,1,3,6,9] ，翻转后应变为 [4,7,2,9,6,3,1] 。（题目来源：https://leetcode-cn.com/problems/invert-binary-tree/description/ ）

最优解（递归解法，Python 代码）

# 定义二叉树节点类
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef invertTree(root):if not root:return None# 交换左右子树root.left, root.right = root.right, root.left# 递归翻转左子树invertTree(root.left)# 递归翻转右子树invertTree(root.right)return root

解析

1. 递归终止条件：当 root 为空节点时，即 not root ，直接返回 None 。因为空树不需要进行翻转操作。
2. 交换左右子树：对于非空节点，使用 root.left, root.right = root.right, root.left 这行代码交换当前节点的左右子树。这是翻转二叉树的核心操作，直接改变了当前节点的子树结构。
3. 递归调用：
   • 交换完当前节点的左右子树后，通过 invertTree(root.left) 递归调用函数自身，对当前节点的左子树进行翻转。这是因为左子树在交换后也需要进一步翻转其内部的子树结构。
   • 同理，通过 invertTree(root.right) 递归调用函数自身，对当前节点的右子树进行翻转。
4. 返回结果：最后返回翻转后的根节点 root ，使得整个翻转操作完成后能得到翻转后的二叉树的根节点，方便后续对整棵树进行操作或访问。

算法复杂度

• 时间复杂度：由于需要对二叉树的每个节点进行一次访问并交换其左右子树，所以时间复杂度为 (O(n)) ，其中 (n) 是二叉树的节点数。
• 空间复杂度：在递归过程中，递归调用栈的深度最大为二叉树的高度 (h) 。在最坏情况下（二叉树为单链表形式），高度 (h = n) ，此时空间复杂度为 (O(n)) ；在最好情况下（二叉树为完全平衡树），高度 (h = \log n) ，空间复杂度为 (O(\log n)) 。

题目描述

给定二叉树的根节点 root，求该二叉树的最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数 。例如，对于二叉树 [3,9,20,null,null,15,7] ，其最大深度为 3，因为从根节点 3 到叶子节点 15 或 7 的路径长度最长，为 3 。（题目来源：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree ）

最优解（递归解法，Python 代码）

# 定义二叉树节点类
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef maxDepth(root):if not root:return 0left_depth = maxDepth(root.left)right_depth = maxDepth(root.right)return max(left_depth, right_depth) + 1

解析

1. 递归终止条件：当 root 为空节点时，即 not root ，返回 0 。因为空树没有节点，其深度为 0 。
2. 递归计算子树深度：
   • 通过 left_depth = maxDepth(root.left) 递归调用 maxDepth 函数，计算左子树的最大深度，并将结果存储在 left_depth 变量中。这是因为要得到整棵树的最大深度，需要先知道左子树的最大深度情况。
   • 同理，通过 right_depth = maxDepth(root.right) 递归调用 maxDepth 函数，计算右子树的最大深度，并将结果存储在 right_depth 变量中。
3. 计算整棵树的最大深度：整棵树的最大深度等于左子树和右子树中较大的深度值再加 1（加 1 是因为要算上根节点本身） ，通过 return max(left_depth, right_depth) + 1 实现这一计算并返回结果。

算法复杂度

• 时间复杂度：由于需要对二叉树的每个节点进行一次访问，所以时间复杂度为 (O(n)) ，其中 (n) 是二叉树的节点数。
• 空间复杂度：在递归过程中，递归调用栈的深度最大为二叉树的高度 (h) 。在最坏情况下（二叉树为单链表形式），高度 (h = n) ，此时空间复杂度为 (O(n)) ；在最好情况下（二叉树为完全平衡树），高度 (h = \log n) ，空间复杂度为 (O(\log n)) 。

题目描述

给定一个二叉树的根节点 root，求该二叉树的最小深度。二叉树的最小深度是指从根节点到最近叶子节点的最短路径上的节点数。这里的叶子节点是指没有子节点的节点。例如，对于二叉树 [3,9,20,null,null,15,7] ，其最小深度为 2，因为从根节点 3 到叶子节点 9 的路径长度最短，为 2 。（题目来源：https://leetcode-cn.com/problems/minimum - depth - of - binary - tree ）

最优解（Python 递归代码实现）

# 定义二叉树节点类
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef minDepth(root):if not root:return 0# 如果左子树为空，最小深度取决于右子树if not root.left:return minDepth(root.right) + 1# 如果右子树为空，最小深度取决于左子树if not root.right:return minDepth(root.left) + 1left_depth = minDepth(root.left)right_depth = minDepth(root.right)return min(left_depth, right_depth) + 1

解析

1. 递归终止条件：当 root 为空节点时，即 not root ，返回 0 。因为空树没有节点，其深度为 0 。
2. 特殊情况处理：
   • 当左子树为空时，此时二叉树的最小深度取决于右子树，通过 if not root.left: return minDepth(root.right) + 1 来计算，这里加 1 是因为要算上根节点本身。
   • 当右子树为空时，此时二叉树的最小深度取决于左子树，通过 if not root.right: return minDepth(root.left) + 1 来计算，同样加 1 是算上根节点。
3. 正常情况递归计算：当左右子树都不为空时，分别通过 left_depth = minDepth(root.left) 和 right_depth = minDepth(root.right) 递归计算左子树和右子树的最小深度，然后取两者中的较小值再加 1（加上根节点） ，即 return min(left_depth, right_depth) + 1 ，得到整棵树的最小深度。

算法复杂度

• 时间复杂度：算法需要遍历二叉树的每个节点，所以时间复杂度为 (O(n)) ，其中 (n) 是二叉树的节点数。
• 空间复杂度：在递归过程中，递归调用栈的深度最大为二叉树的高度 (h) 。在最坏情况下（二叉树为单链表形式），高度 (h = n) ，此时空间复杂度为 (O(n)) ；在最好情况下（二叉树为完全平衡树），高度 (h = \log n) ，空间复杂度为 (O(\log n)) 。

题目描述

1. 序列化：给定一棵二叉树的根节点 root，将其按照某种规则转换为一个字符串，这个过程就是序列化。序列化的目的是将二叉树的数据结构以一种可存储或传输的形式表示出来。
2. 反序列化：给定一个通过序列化得到的字符串数据，将其重新构建成一棵二叉树，这就是反序列化。要求反序列化得到的二叉树与原始二叉树在结构和节点值上完全一致。 （题目来源：https://leetcode-cn.com/problems/serialize - and - deserialize - binary - tree/ ）

最优解（Python 代码实现）

# 定义二叉树节点类
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Codec:def serialize(self, root):"""对二叉树进行序列化"""def dfs(node):if not node:res.append('null')returnres.append(str(node.val))dfs(node.left)dfs(node.right)res = []dfs(root)return ','.join(res)def deserialize(self, data):"""对序列化后的字符串进行反序列化"""def helper():val = next(vals)if val == 'null':return Nonenode = TreeNode(int(val))node.left = helper()node.right = helper()return nodevals = iter(data.split(','))return helper()
# 示例用法
# codec = Codec()
# root = TreeNode(1)
# root.left = TreeNode(2)
# root.right = TreeNode(3)
# root.right.left = TreeNode(4)
# root.right.right = TreeNode(5)
# serialized = codec.serialize(root)
# deserialized_root = codec.deserialize(serialized)

解析

1. 定义二叉树节点类：首先定义 TreeNode 类，用于表示二叉树的节点，每个节点包含节点值 val ，以及指向左子节点 left 和右子节点 right 的指针。
2. 序列化方法 serialize
   • 内部定义了深度优先搜索（DFS）辅助函数 dfs 。在 dfs 函数中，当遇到空节点时，向结果列表 res 中添加 'null' ，表示空节点。当遇到非空节点时，将节点值转换为字符串添加到 res 中，然后递归调用 dfs 分别处理左子树和右子树。
   • 最后通过 ','.join(res) 将结果列表中的元素以逗号连接成字符串，得到序列化后的结果。
3. 反序列化方法 deserialize
   • 内部定义了辅助函数 helper 。helper 函数通过 next(vals) 从迭代器 vals 中获取下一个值。如果获取到的值是 'null' ，表示当前节点为空，返回 None 。
   • 如果获取到的值不是 'null' ，则创建一个新的 TreeNode 节点，其值为获取到的值转换后的整数。然后递归调用 helper 分别构建左子树和右子树，最后返回构建好的节点。
   • 通过 vals = iter(data.split(',')) 将输入的序列化字符串按逗号分割后转换为迭代器，方便 helper 函数依次获取节点值或 'null' 标识，最终返回反序列化构建好的二叉树的根节点。

算法复杂度

• 序列化时间复杂度：在序列化过程中，对二叉树的每个节点进行一次访问，时间复杂度为 (O(n)) ，其中 (n) 是二叉树的节点数。
• 反序列化时间复杂度：反序列化时，同样要处理序列化字符串中的每个元素（对应二叉树的节点或空节点标识），时间复杂度也是 (O(n)) 。
• 空间复杂度：无论是序列化还是反序列化，在递归过程中，递归调用栈的深度最大为二叉树的高度 (h) 。在最坏情况下（二叉树为单链表形式），高度 (h = n) ，此时空间复杂度为 (O(n)) ；在最好情况下（二叉树为完全平衡树），高度 (h = \log n) ，空间复杂度为 (O(\log n)) 。此外，序列化结果存储也需要 (O(n)) 的空间。