（e2）中序遍历
彻底搞懂中序遍历的递归与迭代，吃透边界与复杂度
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
（e2）中序遍历
彻底搞懂中序遍历的递归与迭代，吃透边界与复杂度
递归
上一节我们写出了 `inorder(node.left)`——一个函数在自己体内调用自己。这凭什么合法？它又何时停下？让我们把递归拆开看。
每层套娃装着更小的同款，最里层实心不可拆——对应终止条件
观察
上页我们用递归写出了中序遍历，但「能跑通」和「看透它」是两回事。这一页我们停下来观察——亲自跟一次遍历过程，看它到底按什么顺序访问节点，又会暴露哪些隐藏性质。
字典页天然按拼音升序；BST 中序天然按 key 升序——本质都是「已排好序」的产物
思路
上一页我们看到递归骨架——两次自我调用夹一次「访问」。现在把观察凝成思路：中序遍历的本质是什么、关键判断在哪、以及它最适合解决哪些问题。
BST 左小右大的结构, 让中序天然排出大小序, 像按号就座
构思
观察完示例，我们已经看到访问顺序是先左后右、中间回头。现在要把这个直觉升华为正式定义，并看清它为什么这么有用。
每人先听左边说完、自己再说、再听右边——自己的话正好落在中间
实现
前面想清楚了「左、根、右」的访问思路，但要写成能跑的代码，还得把入栈时机、空指针判定这些细节钉死。这一页把递归、迭代、Morris 三种写法摊开，顺便讲最容易踩的坑。
沿左墙一路走到底、走不通回头才处理路口（节点）、再探右岔路
实例
代码已经写好，但单看 inorder 三行还是会绕——下面用一棵具体的树，手动展开递归调用栈，看中序遍历到底按什么顺序访问节点。
中序天然按「左小右大」访问，输出就是已排好的字典
分摊分析
储值卡 1000 元喝 50 杯咖啡——看似贵，分摊到每杯 20 元且事先能算清。这就是分摊思想：不看一次性大开销，看连续操作每次的稳定代价。Morris 遍历正是用它证明整体线性。
一次投入 1000 元，50 次用完，每次确定花 20 元，不是「可能」
本节要点
- ✓中序遍历即「左→根→右」的递归定义，不依赖具体实现
- ✓递归与显式栈完全等价，时空复杂度同为 O(n)
- ✓Morris 遍历借叶子空指针把辅助空间压到 O(1)
- ✓对 BST，中序结果即为升序，是验证 BST 的天然工具
课后思考
先凭直觉作答，再对照参考答案；想不出来比答错更值得停下来。
参考答案中序按左→根→右访问。BST 定义左子树都小于根、右子树都大于根，因此所有节点恰好按从小到大被访问一次。这是结构定义与访问顺序的天然契合。
参考答案仍能完整访问每个节点一次。适用于表达式语法树求值、文件系统目录展开等任何'先处理完左侧、再处理根、再处理右侧'的场景。
参考答案仍能完整访问所有节点，但需要约定相等键放左还是放右；不同约定会得到不同序列，调整关键是统一相等键的处理规则。