递归

副标题 / 摘要 LeetCode 114 的真正难点不是把树“拍平”，而是想清楚重连顺序。只要抓住“目标链表等于先序遍历顺序”，再把处理方向反过来，prev 指针会让整题变成一段非常稳定的原地递归。 预计阅读时长：12~15 分钟 标签：Hot100、二叉树、先序遍历、原地修改、递归 SEO 关键词：Flatten Binary Tree to Linked List, 二叉树展开为链表, 先序遍历, 原地修改, 反向先序, LeetCode 114 元描述：系统讲透 LeetCode 114 的反向先序重连思路，解释 prev 指针为什么有效，并补充工程迁移、复杂度与进阶 O(1) 方案。 A — Algorithm（题目与算法） 题目还原 给你一棵二叉树，请把它原地展开成一个“只沿 right 指针连接”的单链表。 展开后要满足两条规则： 每个节点的 left 都必须变成 null 沿 right 走出来的顺序，必须与原树的先序遍历顺序完全一致 输入输出 名称 类型 描述 root TreeNode 二叉树根节点 返回值 无 原地修改 root 示例 1 输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6] 示例 2 输入：root = [] 输出：[] 示例 3 输入：root = [0] 输出：[0] 提示 树中结点数在范围 [0, 2000] 内 -100 <= Node.val <= 100 进阶 你可以使用原地算法（O(1) 额外空间）展开这棵树吗？ ...

副标题 / 摘要 LeetCode 108 的关键不在“会递归”，而在于看懂题目同时要求两件事：既要保持 BST 的有序性，又要尽量平衡。只要抓住“中点做根”这个证据，整题就会自然落成一个非常干净的区间分治。 预计阅读时长：11~14 分钟 标签：Hot100、二叉树、BST、分治、递归 SEO 关键词：Convert Sorted Array to Binary Search Tree, 将有序数组转换为二叉搜索树, 平衡二叉搜索树, BST, 分治, LeetCode 108 元描述：系统讲透 LeetCode 108 的中点分治构造法，覆盖题意推导、正确性解释、工程映射与多语言实现。 A — Algorithm（题目与算法） 题目还原 给你一个严格递增的整数数组 nums，请把它转换成一棵高度平衡的二叉搜索树。 这里同时包含两个目标： 新树必须满足 BST 的大小关系 新树还必须尽量平衡，也就是任意节点左右子树高度差不超过 1 输入输出 名称 类型 描述 nums int[] 严格递增数组 返回值 TreeNode 任意一棵合法的高度平衡 BST 根节点 示例 1 输入：nums = [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5] 解释：[0,-10,5,null,-3,null,9] 也同样正确。 示例 2 输入：nums = [1,3] 输出：[3,1] 解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。 提示 1 <= nums.length <= 10^4 -10^4 <= nums[i] <= 10^4 nums 按严格递增顺序排列 目标读者 正在刷 Hot100，希望把“数组转树”的分治模板固定下来的学习者 已经会写 BST 判断，但还不够熟悉“BST 构造题”如何从题意推出来的开发者 想理解为什么“中点做根”不是技巧，而是由约束直接逼出来的读者 背景 / 动机 这题很适合拿来训练一个能力： ...

副标题 / 摘要 翻转二叉树是一道看起来非常短、却能快速检验你是否真正理解递归结构的题。本文围绕 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) 反转单链表，附递归对比、工程迁移与多语言实现。 A — Algorithm（题目与算法） 题目还原 给你单链表的头节点 head，请你反转链表，并返回反转后的链表。 输入输出 名称 类型 描述 head ListNode 单链表头节点（可能为空） 返回 ListNode 反转后的新头节点 示例 1（自拟） 输入: 1 -> 2 -> 3 -> 4 -> 5 -> null 输出: 5 -> 4 -> 3 -> 2 -> 1 -> null 示例 2（自拟） 输入: 1 -> 2 -> null 输出: 2 -> 1 -> null 目标读者 正在刷 Hot100 / 准备面试的同学 写链表题经常断链/空指针、希望建立稳定模板的中级开发者 需要在 C/C++/Rust 等语言里熟练处理指针与所有权的工程师 背景 / 动机 在真实工程里，“反转链表”不一定以 LeetCode 的形态出现，但它背后的能力非常通用： ...

副标题 / 摘要 循环常依赖可变变量，而递归可以用参数传递状态。本文展示转换思路与适用场景。 目标读者 学习函数式编程的开发者 想减少可变状态的人 关注代码可推理性的工程师 背景 / 动机 可变状态会降低可推理性并增加错误。 递归可以把状态显式化，从而更安全。 核心概念 递归：函数调用自身 累加器：用参数传递中间状态 不可变性：避免状态被修改 实践指南 / 步骤 找出循环中的状态变量 把状态变量变成参数 定义终止条件 返回最终结果 可运行示例 # 循环版本 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） 检查你的递归函数，确认终止条件是否足够严格。