递归

副标题 / 摘要 翻转二叉树是一道看起来非常短、却能快速检验你是否真正理解递归结构的题。本文围绕 LeetCode 226 拆解“交换左右子树”的本质，给出递归 / BFS 两种做法，以及结构镜像在工程中的迁移思路。 预计阅读时长：8~10 分钟 标签：Hot100、二叉树、递归、BFS、树变换 SEO 关键词：Hot100, Invert Binary Tree, 翻转二叉树, 树镜像, 递归, LeetCode 226 元描述：讲清 LeetCode 226 的递归与 BFS 解法，并延伸到布局镜像、结构变换等工程场景。 目标读者 想检验自己是否真正理解“递归作用在整棵树每个节点上”的刷题读者 看到树题就下意识写遍历，但不确定该在什么时机处理当前节点的开发者 需要做树形结构镜像、布局翻转或对称转换的工程师 背景 / 动机 226 的代码通常很短，但它的思维非常典型： 当前节点要做什么？ 把 left 和 right 交换。 子问题是什么？ 左右子树本身也都要继续翻转。 这就是非常纯粹的“当前操作 + 递归处理子问题”。 如果你对这题没有完全吃透，往往会出现： 只交换根节点，不继续处理子树 交换后递归方向写乱 把本来能原地完成的事，额外重建一棵新树 核心概念 树镜像（mirror）：把每个节点的左子树与右子树对调 原地变换（in-place transform）：不新建整棵树，只交换指针 递归分治：当前节点处理完后，左右子树仍是同类型问题 BFS 层序变换：也可以按层把每个节点的左右孩子交换 A — Algorithm（题目与算法） 题目还原 给你一棵二叉树的根节点 root，请将这棵树翻转，并返回翻转后的根节点。 输入输出 名称 类型 描述 root TreeNode 二叉树根节点，可以为空 返回值 TreeNode 翻转后的根节点 示例 1 输入: root = [4,2,7,1,3,6,9] 输出: [4,7,2,9,6,3,1] 解释: 原树左右子树整体对调后，所有节点都完成镜像翻转。 示例 2 输入: root = [2,1,3] 输出: [2,3,1] 示例 3 输入: root = [] 输出: [] 约束 树中节点数目在 [0, 100] 内 -100 <= Node.val <= 100 C — Concepts（核心思想） 思路推导：为什么“交换 + 递归”就够了 假设当前节点是 node，我们要做的事情只有两步： ...

副标题 / 摘要 “最大深度”是树递归最标准的起手式。你只要真正理解“当前树的答案依赖左右子树答案”的定义，整类树形 DP / DFS 题都会顺很多。本文以 LeetCode 104 为核心，系统讲解递归 DFS、层序 BFS 与工程迁移方法。 预计阅读时长：9~11 分钟 标签：Hot100、二叉树、DFS、BFS、递归 SEO 关键词：Hot100, Maximum Depth of Binary Tree, 二叉树的最大深度, DFS, BFS, LeetCode 104 元描述：从深度定义出发，讲清 LeetCode 104 的 DFS 和 BFS 解法，并附多语言可运行代码。 目标读者 刚开始刷树题，想把“树递归返回值”真正吃透的同学 能写遍历，但一遇到“求高度 / 求路径 / 求答案”就容易混乱的开发者 需要在菜单树、组织架构、嵌套 JSON 等层级数据里做深度分析的工程师 背景 / 动机 LeetCode 104 看起来像一道“送分题”，但它几乎是所有树递归的母题： 你需要先回答“空树深度是多少” 再回答“当前节点的答案依赖谁” 最后把关系写成 1 + max(left, right) 一旦这个递归定义真正建立起来，后续的平衡二叉树、直径、路径和、最近公共祖先都会更容易进入状态。 核心概念 深度 / 高度：这里按题意，根到最远叶子节点的节点数 后序式思维：想知道当前节点答案，必须先知道左右子树答案 DFS：递归向下，回溯时组合答案 BFS：按层遍历，最后一层编号就是树深度 A — Algorithm（题目与算法） 题目还原 给定二叉树根节点 root，返回其 最大深度。 ...

副标题 / 摘要 反转链表是“指针重连”的入门必修课：看似简单，却最容易因为边界、断链、顺序写错而翻车。本文用 ACERS 结构把三指针迭代写法讲透，并给出递归对照与多语言可运行实现。 预计阅读时长：10~12 分钟 标签：Hot100、链表、指针、迭代 SEO 关键词：Hot100, Reverse Linked List, 反转链表, 三指针, 迭代, 递归, LeetCode 206 元描述：三指针迭代 O(n)/O(1) 反转单链表，附递归对比、工程迁移与多语言实现。 目标读者 正在刷 Hot100 / 准备面试的同学 写链表题经常断链/空指针、希望建立稳定模板的中级开发者 需要在 C/C++/Rust 等语言里熟练处理指针与所有权的工程师 背景 / 动机 在真实工程里，“反转链表”不一定以 LeetCode 的形态出现，但它背后的能力非常通用： 你要在 O(1) 额外空间 下重排节点顺序（例如复用节点对象，避免额外分配） 你要理解 指针重连的顺序：先保留 next，再改 cur.next，否则就会断链 你要能写出 不会特判地狱、对 head = null 也稳的实现 把这题做成模板后，很多链表题（如反转区间、k 组反转、判断回文链表）都会变得顺手很多。 核心概念 单链表：每个节点只有一个 next 指针指向后继 断链风险：一旦把 cur.next 改掉而没保存原来的 next，就丢失后半段 三指针（prev / cur / next）：用 next 暂存后继，再把 cur.next 指向 prev 循环不变量：prev 永远指向“已反转部分”的头；cur 永远指向“未处理部分”的头 A — Algorithm（题目与算法） 题目还原 给你单链表的头节点 head，请你反转链表，并返回反转后的链表。 ...

副标题 / 摘要 循环常依赖可变变量，而递归可以用参数传递状态。本文展示转换思路与适用场景。 目标读者 学习函数式编程的开发者 想减少可变状态的人 关注代码可推理性的工程师 背景 / 动机 可变状态会降低可推理性并增加错误。 递归可以把状态显式化，从而更安全。 核心概念 递归：函数调用自身 累加器：用参数传递中间状态 不可变性：避免状态被修改 实践指南 / 步骤 找出循环中的状态变量 把状态变量变成参数 定义终止条件 返回最终结果 可运行示例 # 循环版本 def sum_loop(nums): s = 0 for x in nums: s += x return s # 递归版本 def sum_rec(nums, acc=0): if not nums: return acc return sum_rec(nums[1:], acc + nums[0]) if __name__ == "__main__": print(sum_loop([1, 2, 3])) print(sum_rec([1, 2, 3])) 解释与原理 循环依赖可变变量 s，递归用参数 acc 传递状态。 这样状态是显式的，减少副作用。 常见问题与注意事项 递归一定更好吗？ 不一定，深度过大会栈溢出。 ...

副标题 / 摘要 尾递归可以把递归的“返回工作”提前完成，从而具备优化潜力。本文用阶乘示例说明概念与限制。 目标读者 学习递归与函数式思想的开发者 需要写可读性强的算法代码的人 关注性能的工程师 背景 / 动机 普通递归在返回阶段仍需要计算，导致栈帧无法复用。 尾递归把“结果累积”放在参数里，使返回阶段无需额外计算。 核心概念 尾递归：递归调用是函数的最后一步 累加器：把中间结果传入下一层 尾调用优化（TCO）：编译器复用栈帧 实践指南 / 步骤 把中间结果写成累加器参数 让递归调用成为最后一步 确认语言是否支持尾调用优化 在不支持 TCO 的语言改为迭代 可运行示例 def fact_tail(n: int, acc: int = 1) -> int: if n <= 1: return acc return fact_tail(n - 1, acc * n) if __name__ == "__main__": print(fact_tail(5)) 解释与原理 尾递归把计算提前完成，返回阶段只需返回结果。 若语言支持 TCO，就能复用栈帧，避免栈溢出。 常见问题与注意事项 Python 支持 TCO 吗？ 不支持，所以深度大仍会栈溢出。 尾递归一定快吗？ 取决于语言与编译器优化。 何时改为迭代？ 当递归深度不可控时。 最佳实践与建议 尾递归用于可读性与函数式风格 在生产中评估语言是否支持 TCO 大规模递归优先使用迭代 小结 / 结论 尾递归提供了优化潜力，但效果依赖语言支持。 理解其形式有助于写出更清晰的递归代码。 ...

副标题 / 摘要 栈溢出通常由无限递归或过深调用导致。本文用可运行示例解释原因与规避策略。 目标读者 学习递归与算法的开发者 关注性能与稳定性的工程师 需要理解运行时限制的初学者 背景 / 动机 每次函数调用都会占用栈空间。 当调用深度超过上限，程序会抛出栈溢出错误或崩溃。 核心概念 调用栈：保存函数调用上下文 递归深度：递归层数过深会耗尽栈 尾递归优化：某些语言可复用栈帧 实践指南 / 步骤 确保递归有明确终止条件 控制递归深度或改为迭代 对深度递归设定保护阈值 在高风险路径做测试 可运行示例 import sys sys.setrecursionlimit(1000) def boom(n): return boom(n + 1) if __name__ == "__main__": try: boom(0) except RecursionError as e: print("stack overflow:", e) 解释与原理 每次递归都会压入新的栈帧。 当深度超过解释器或系统限制时，就会触发栈溢出。 常见问题与注意事项 提高递归深度就能解决吗？ 只能延迟问题，不能根治。 尾递归一定不会溢出吗？ 取决于语言是否支持尾递归优化。 迭代一定更好吗？ 不一定，但在深度很大时更安全。 最佳实践与建议 用迭代替代深度递归 为递归函数加入深度保护 对递归路径做压力测试 小结 / 结论 栈溢出是递归深度过大导致的运行时问题。 通过终止条件、迭代替换与深度限制可以有效避免。 参考与延伸阅读 Python Recursion Limit The Art of Computer Programming 元信息 阅读时长：5~7 分钟 标签：递归、栈溢出 SEO 关键词：栈溢出, 递归深度 元描述：解释栈溢出的成因与规避方式。 行动号召（CTA） 检查你的递归函数，确认终止条件是否足够严格。