栈

副标题 / 摘要 二叉树遍历是树题模板的起点，中序遍历则是“递归思维”和“显式栈模拟”最典型的一题。本文按 ACERS 结构拆解 LeetCode 94，把左-根-右的访问顺序、迭代栈写法和工程迁移价值一次讲清。 预计阅读时长：10~12 分钟 标签：Hot100、二叉树、DFS、栈、中序遍历 SEO 关键词：Hot100, Binary Tree Inorder Traversal, 二叉树的中序遍历, 中序遍历, 显式栈, LeetCode 94 元描述：从递归到显式栈，系统讲透 LeetCode 94 二叉树中序遍历，并给出工程场景迁移与多语言实现。 目标读者 正在刷 Hot100，希望把树遍历模板固定下来的同学 刚从数组 / 链表过渡到树结构，容易把前序、中序、后序顺序写混的开发者 需要在 BST、表达式树、抽象语法树里复用“左-根-右”思想的工程师 背景 / 动机 中序遍历本身不复杂，但它的训练价值很高： 它是“递归 = 隐式栈，迭代 = 显式栈”最容易建立直觉的一题 它能帮助你稳定掌握“先一路向左，再回退访问根，再转向右子树”的过程 在 二叉搜索树（BST） 里，中序遍历天然得到有序序列，工程迁移价值很强 很多人第一次写树题不是逻辑不会，而是： 不清楚访问顺序到底是谁先谁后 迭代版不知道什么时候入栈、什么时候出栈 一旦树为空或只有单边链，代码就容易写乱 这题把模板练熟，后面的验证 BST、找第 k 小元素、恢复二叉搜索树等题会更顺。 核心概念 中序遍历：按照 左子树 -> 根节点 -> 右子树 的顺序访问 DFS（深度优先搜索）：树遍历最常见的组织方式，中序遍历就是 DFS 的一种访问顺序 显式栈：把递归调用栈手动写出来，用栈保存“回头还要处理的节点” 树高 h：空间复杂度通常写成 O(h)，平衡树约为 O(log n)，极端退化链表时是 O(n) A — Algorithm（题目与算法） 题目还原 给定二叉树根节点 root，返回它的 中序遍历 结果。 ...

副标题 / 摘要 只有队列（FIFO）时，也能实现栈（LIFO）。本文展示单队列旋转法，并分析复杂度与边界。 目标读者 刷题与面试准备的开发者 需要理解数据结构转换的人 初中级算法学习者 背景 / 动机 栈的后进先出与队列的先进先出相反。 “旋转队列”可以把最新元素移动到队头，从而模拟栈顶。 核心概念 队列（FIFO）：先进先出 栈（LIFO）：后进先出 队列旋转：把新元素转到队首 实践指南 / 步骤 入栈：将元素入队 旋转队列：把队首依次出队再入队，直到新元素位于队首 出栈：直接出队 取栈顶：查看队首 可运行示例 from collections import deque class MyStack: def __init__(self): self.q = deque() def push(self, x: int) -> None: self.q.append(x) for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self) -> int: return self.q.popleft() def top(self) -> int: return self.q[0] def empty(self) -> bool: return not self.q if __name__ == "__main__": s = MyStack() s.push(1) s.push(2) print(s.top()) print(s.pop()) print(s.empty()) 解释与原理 每次 push 后旋转队列，使新元素位于队首。 这样 pop 就相当于弹出“栈顶”。 ...

副标题 / 摘要 当系统只提供栈（LIFO）时，如何构建队列（FIFO）？本文用双栈法给出清晰实现与工程要点。 目标读者 刷题与面试准备的开发者 需要理解数据结构转换的人 希望掌握复杂度分析的初中级工程师 背景 / 动机 队列的先进先出与栈的后进先出相反。 双栈法通过“翻转顺序”实现队列语义，是经典的结构变换题。 核心概念 栈（LIFO）：后进先出 队列（FIFO）：先进先出 双栈翻转：把输入顺序倒置为输出顺序 实践指南 / 步骤 入队：压入 in 栈 出队/取队首：若 out 栈为空，将 in 栈全部弹出并压入 out 栈 从 out 栈弹出：即为队首 保持延迟搬运：只在 out 为空时搬运 可运行示例 class MyQueue: def __init__(self): self._in = [] self._out = [] def push(self, x: int) -> None: self._in.append(x) def _move(self) -> None: if not self._out: while self._in: self._out.append(self._in.pop()) def pop(self) -> int: self._move() return self._out.pop() def peek(self) -> int: self._move() return self._out[-1] def empty(self) -> bool: return not self._in and not self._out if __name__ == "__main__": q = MyQueue() q.push(1) q.push(2) print(q.peek()) print(q.pop()) print(q.empty()) 解释与原理 in 栈负责“输入顺序”，out 栈负责“输出顺序”。 当 out 为空时，把 in 全部倒入 out，就实现了 FIFO 的逆序输出。 ...

副标题 / 摘要 栈溢出通常由无限递归或过深调用导致。本文用可运行示例解释原因与规避策略。 目标读者 学习递归与算法的开发者 关注性能与稳定性的工程师 需要理解运行时限制的初学者 背景 / 动机 每次函数调用都会占用栈空间。 当调用深度超过上限，程序会抛出栈溢出错误或崩溃。 核心概念 调用栈：保存函数调用上下文 递归深度：递归层数过深会耗尽栈 尾递归优化：某些语言可复用栈帧 实践指南 / 步骤 确保递归有明确终止条件 控制递归深度或改为迭代 对深度递归设定保护阈值 在高风险路径做测试 可运行示例 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） 检查你的递归函数，确认终止条件是否足够严格。

副标题 / 摘要 栈与堆是两种常见的内存分配模型。本文解释它们在生命周期、分配成本与适用场景上的差异。 目标读者 想理解内存模型的开发者 需要优化性能与内存的工程师 学习语言底层机制的同学 背景 / 动机 很多性能问题来自对内存模型的误解。 理解栈与堆能帮助你写出更稳定、更高效的代码。 核心概念 栈（Stack）：函数调用时自动分配，LIFO 堆（Heap）：运行期动态分配，需要显式释放或 GC 生命周期：栈随作用域结束自动释放 实践指南 / 步骤 局部临时数据优先放栈 需要跨作用域共享的对象放堆 避免频繁堆分配 关注 GC 或释放成本 在性能关键路径上减少堆对象 可运行示例 #include <stdio.h> #include <stdlib.h> int main(void) { int a = 10; // 栈上 int *p = malloc(sizeof(int)); // 堆上 *p = 20; printf("%d %d\n", a, *p); free(p); return 0; } 解释与原理 栈分配快、释放自动，但生命周期短。 堆分配更灵活，但成本高且需要额外管理（GC 或 free）。 常见问题与注意事项 栈一定更快吗？ 一般更快，但栈空间有限。 堆对象一定要手动释放吗？ 取决于语言，有 GC 的语言会自动回收。 栈溢出是什么？ 递归过深或局部变量过大导致栈空间耗尽。 最佳实践与建议 频繁创建对象时考虑对象池 对大对象避免放在栈上 监控 GC 压力与分配热点 小结 / 结论 栈与堆的差异决定了性能与内存管理策略。 理解内存模型是写出稳定系统的基础。 ...