（e1）先序遍历
递归思路、迭代写法、边界用例一次打通
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
（e1）先序遍历
递归思路、迭代写法、边界用例一次打通
转化策略
先序遍历讲的是「按什么顺序访问节点」。但要把一整棵树真正落成一段可存储、可传输、可还原的序列，光有顺序还不够——我们需要一套完整的转化策略。
先记外盒(根)，再拆左右小盒(子树)；空盒要打标记，否则装不回去
遍历规则
上一页我们讨论了把树压成序列的转化策略。现在回到规则本身：为什么「根→左→右」这个顺序被叫「先」序？
先看大厅（根），再进左边房间（左子树），最后进右边（右子树）；每进一个新空间，规则都重走一遍
递归实现
上一页我们看清了先序遍历的路线——根、左、右。怎么让程序自己按这条路线走下去？递归就够了。
大娃套小娃，直到空娃；大调用嵌小调用，直到空节点
迭代实现（1）
上一页我们用递归写了先序遍历——三行就完事。但递归调用栈是系统隐式管的，看不见也控不住。树太深就会爆栈，想暂停或并行也无从下手。这页我们自己造一个栈来替代它。
想让左边文件先抽到，就把它放在最上面——右边的必须压在下面
实例
递归和迭代都给了框架，但只看代码还是会绕。这一页拿一棵具体的二叉树，把「根 → 左 → 右」落到真实节点上，再看这种顺序能用来做什么。
进文件夹先看当前内容(根)，再从左到右打开子文件夹(左→右)，全部展开后才退出
新思路
看完了实例，你会觉得先序遍历只是树的专属动作。但把视角抬高一层你发现：核心不是树，而是「根先于子 + 递归骨架」。这一页聊聊它如何升维，套到更多题目上。
不论什么零件，「先本工位→再下一工位」的顺序不变，换的只是每站的具体操作。
新构思
看完了实例，你可能想问：递归和栈都要 O(h) 空间，能不能更省？Morris 遍历的答案是借树自己的空指针，把「回头的路」写在树里。
书看完必须放回原位，临时指针走完左子树也要拆掉
迭代实现（2）
迭代实现（1）用栈手动模拟——三种遍历要写三个版本，差别只在压栈顺序。今天换个思路：每个节点入栈两次，把「路过」和「真正处理」分两步做，同一份代码就能产出三种遍历。
首次过节点是列提纲（只压孩子）；再次过节点是真读（输出）
本节要点
- ✓先序遍历的判据是'根先于子树'，与左右子树的相对顺序无关
- ✓迭代用栈模拟递归：先压右再压左，弹出顺序才是真正的访问顺序
- ✓递归与迭代遍历同一棵树的序列完全相同，只是控制流表达不同
- ✓前/中/后序的区别仅在根的访问时机，对同一棵树三者序列互不相同
课后思考
先独立写下思路，再展开参考答案，比较自己的推理路径。
参考答案根是当前子树的入口。先处理根能留下“已访问边界”，供栈回溯；若先处理子树，根的信息容易被覆盖或难以确定回溯位置。
参考答案可把“递归调用尚未结束”视为栈中任务。弹出一个任务时，先完成根，再按逆序压入右、左任务；后压入的左任务会先执行。
参考答案“根先于后代”仍成立。每棵树先访问根，再按预先约定的次序访问各子树；若不约定子树次序，同一棵树可能对应多种遍历结果。