中序遍历

副标题 / 摘要 二叉树遍历是树题模板的起点，中序遍历则是“递归思维”和“显式栈模拟”最典型的一题。本文按 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，返回它的 中序遍历 结果。 ...