从汉诺塔到面试刷题：用C++递归模板搞定LeetCode‘爬楼梯’‘二叉树遍历’

从汉诺塔到面试刷题：用C++递归模板搞定LeetCode‘爬楼梯’‘二叉树遍历’

第一次接触递归时，很多人都会被那种"自己调用自己"的魔法般特性所震撼。汉诺塔作为递归算法的经典案例，完美展示了如何将复杂问题分解为相同结构的子问题。但真正让递归在技术面试中大放异彩的，是它解决各类算法问题的通用性——从简单的爬楼梯到复杂的树形结构遍历，递归思维都能提供优雅的解决方案。

1. 汉诺塔：递归思维的启蒙案例

汉诺塔问题看似简单，却蕴含着递归思想的精髓。当我们需要将n个盘子从A柱移动到C柱时，整个过程可以分解为三个关键步骤：

1. 将上面的n-1个盘子从A经过C移动到B（临时柱）
2. 将第n个盘子直接从A移动到C
3. 将那n-1个盘子从B经过A移动到C

这个分解过程揭示了一个重要规律：解决大规模问题的方法，就是先解决它的子问题。在C++中，这种思想可以简洁地表达为：

void hanoi(int n, char from, char via, char to) { if (n == 1) { cout << "Move disk 1 from " << from << " to " << to << endl; return; } hanoi(n-1, from, to, via); cout << "Move disk " << n << " from " << from << " to " << to << endl; hanoi(n-1, via, from, to); }

这段代码中，我们可以提炼出递归函数的四个核心要素：

• 终止条件：当n=1时直接移动
• 参数定义：n表示盘子数量，from/via/to表示三根柱子
• 递推关系：通过n-1分解问题
• 递归调用：两次调用自身处理子问题

提示：理解递归的关键是相信函数能正确处理子问题，而不需要深入每一层调用细节。

2. 递归模板：从汉诺塔到通用解法

基于汉诺塔的经验，我们可以建立一个适用于大多数递归问题的C++模板框架：

ReturnType recursiveFunction(Parameters) { // 1. 终止条件 if (baseCase) { return baseResult; } // 2. 处理当前层逻辑 processCurrentLevel(); // 3. 递归调用处理子问题 SubResult sub = recursiveFunction(modifiedParameters); // 4. 合并结果并返回 return combineResults(sub); }

让我们用这个模板重新审视汉诺塔的实现：

这个模板的强大之处在于它的通用性。接下来我们将看到，它同样适用于解决LeetCode中的经典递归问题。

3. 实战应用：LeetCode递归问题解析

3.1 爬楼梯问题（LeetCode 70）

问题描述：每次可以爬1或2个台阶，问爬到第n阶有多少种不同的方法。

用我们的递归模板分析：

1. 终止条件：当n=1时只有1种方法，n=2时有2种方法
2. 递推关系：到达第n阶的方法数等于到达n-1阶和n-2阶方法数之和
3. 递归调用：分别计算n-1和n-2的情况
4. 合并结果：将两个子问题的结果相加

实现代码：

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

虽然这个解法直观，但存在重复计算问题。我们可以通过记忆化优化：

unordered_map<int, int> memo; int climbStairs(int n) { if (n <= 2) return n; if (memo.find(n) != memo.end()) return memo[n]; memo[n] = climbStairs(n-1) + climbStairs(n-2); return memo[n]; }

3.2 二叉树的前序遍历（LeetCode 144）

二叉树遍历是递归应用的另一个典型场景。以前序遍历为例：

1. 终止条件：当前节点为空
2. 处理当前层：访问根节点值
3. 递归调用：分别遍历左子树和右子树
4. 合并结果：将结果存入vector

实现代码：

void preorder(TreeNode* root, vector<int>& res) { if (!root) return; // 终止条件 res.push_back(root->val); // 处理当前层 preorder(root->left, res); // 递归左子树 preorder(root->right, res); // 递归右子树 } vector<int> preorderTraversal(TreeNode* root) { vector<int> res; preorder(root, res); return res; }

三种基本遍历方式的递归结构对比：

4. 递归优化与复杂度分析

递归虽然优雅，但可能面临栈溢出和重复计算的问题。常见的优化策略包括：

• 记忆化：存储已计算结果避免重复计算
• 尾递归优化：某些编译器可优化尾递归为迭代
• 迭代转换：用栈模拟递归调用过程

以斐波那契数列为例，对比不同实现的时间复杂度：

理解递归的时间复杂度通常需要分析递归树。以汉诺塔为例：

• 每个问题分解为2个子问题
• 递归深度为n
• 总时间复杂度为O(2^n)

对于二叉树遍历：

• 每个节点访问一次
• 时间复杂度为O(n)
• 空间复杂度取决于树高，最坏O(n)

在实际面试中，能够清晰分析递归算法的复杂度是重要的加分项。建议在写出递归解法后，主动讨论其时间空间复杂度，并考虑优化可能性。