数据结构高频算法题 订阅+ 进入阅读模式

数据结构算法题中，递归与非递归实现的对比是考研高频考点，以下精选 8 道核心题型，解析两种实现的适用场景与效率差异，附代码示例。

一、二叉树遍历（考研必考，占算法题 30%）

1. 前序遍历（根 - 左 - 右）

递归实现：

void preorder(TreeNode* root) {

if(!root) return;

cout <val; // 访问根节点

preorder(root->left);

preorder(root->right);

}

非递归实现（栈辅助）：

void preorder_iter(TreeNode* root) {

stack s;

while(root || !s.empty()) {

while(root) {

cout << root->val;

s.push(root);

root = root->left;

}

root = s.top(); s.pop();

root = root->right;

}

}

对比：递归代码简洁但递归深度过深（如二叉树高度 > 1e4）会栈溢出，非递归更适合大规模数据。

二、斐波那契数列（动态规划入门）

递归实现（效率低，时间复杂度 O (2^n)）：

int fib(int n) {

if(n <= 1) return n;

return fib(n-1) + fib(n-2);

}

非递归实现（迭代，O (n) 时间）：

int fib_iter(int n) {

if(n <= 1) return n;

int a=0, b=1, c;

for(int i=2; i<=n; i++) {

c = a + b;

a = b;

b = c;

}

return c;

}

优化：可用矩阵快速幂将时间复杂度降至 O (logn)，适合 n>1e6 的场景。

三、汉诺塔问题（递归经典应用）

递归实现核心逻辑：

void hanoi(int n, char A, char B, char C) {

if(n == 1) {

cout << "Move " << n << " from " << A << " to " << C << endl;

return;

}

hanoi (n-1, A, C, B); // 将 n-1 个从 A 移到 B

cout << "Move " << n << " from " << A << " to " << C << endl;

hanoi (n-1, B, A, C); // 将 n-1 个从 B 移到 C

}

非递归实现：通过模拟栈帧状态，逻辑复杂但可避免递归限制，步骤数与递归相同（2^n -1）。

其他高频题型：二叉树后序遍历（非递归需标记访问状态）、快速排序（递归简洁，非递归用栈模拟分区）、求二叉树深度（递归一行代码实现）等。复习建议：优先掌握递归思想，理解其 "分解问题 - 终止条件" 核心；非递归实现需熟练运用栈 / 队列辅助，分析时间空间复杂度差异，根据题目约束选择最优方案。