Morris：借空指针，不用栈也不递归
遍历二叉树要么递归（隐式调用栈）、要么显式压一个栈，两者都要 O(h) 的额外空间（h 为树高）。Morris Traversal 把这个额外空间压到 O(1)——它的灵感来自线索二叉树 (threaded binary tree)：一个节点本该为 null 的指针其实是浪费的，可以临时借它指向中序遍历里的「下一个」节点。遍历时在每个节点的中序前驱上装一条线索指回自己，走完左子树顺着线索自动返回，再把线索拆掉。全程不开栈、不递归，遍历结束后树结构原样复原。
本页约定： 节点画成圆圈，圈内是 value。所有演示树都是二叉搜索树 (BST)（左 < 根 < 右），于是中序遍历的结果恰好是升序，方便对照对错。已访问的节点填成实心青色；当前游标 curr 用橙色描边，当前前驱
pred 用粉色描边；临时线索画成粉色虚线箭头。
1 · 线索二叉树：空指针能派上什么用
一棵 n 个节点的二叉树有 n + 1 个空指针（叶子与单边节点留下的 null），它们什么都不指，是纯粹的浪费。线索二叉树的想法是把这些空指针利用起来：本该为空的 right 指针，让它指向该节点的中序后继 (inorder successor)；本该为空的
left 指针，让它指向中序前驱。这样不靠栈也能顺着线索走完整棵树。
Morris 遍历只用到其中一半——right 线索指向中序后继。下面这棵树点「显示中序右线索」，会把每个
right == null 的节点连一条虚线箭头到它的中序后继（那个在升序序列里紧跟其后的节点）。注意：有真实右孩子的节点不需要线索（它的后继在右子树的最左端）；整棵树的最大值没有后继，也没有线索。Morris 的精髓就是：这些线索不预先建好，而是在遍历中临时装上、用完即拆。
为什么是「左子树的最右节点」？ 一个有左子树的节点 X，它的中序前驱是「左子树里最大的那个」，也就是从左孩子一路向右走到底的最右节点。反过来，这个最右节点的中序后继恰好就是 X。所以 Morris 在「X 的左子树最右节点」上装一条指回 X 的线索——走完 X 的整个左子树，自然会落到这个最右节点，顺着线索就跳回 X，不需要任何栈来记「回头路」。
2 · 单步：看线索一条条装上、又一条条拆掉
下面单步执行完整的 Morris 遍历。游标 curr 从根出发，每一步只做一件事：
curr 没有左子树 → 直接访问 curr，然后沿 right 前进（这条 right 可能是真实孩子，也可能是上一轮装的线索）。
curr 有左子树 → 先在左子树里一路向右，找到最右节点 pred（curr 的中序前驱），看它的 right:
- right 为空 → 第一次到达 curr。装线索
pred.right = curr记住回头路，curr 下行到左子； - right 已指回 curr → 顺着线索回来了，左子树已走完。拆掉线索还原，然后沿 right 前进。
内层那个「找最右」的循环里，用 pred.right != curr 区分这是第一次来（该装线索） 还是回来了（该拆线索）——这是整个算法唯一需要想清楚的判断。
中序与前序只差一行。「访问」节点的时机不同：中序在拆线索 / 没有左子树时访问（左子树先走完）；前序在装线索 / 没有左子树时访问（下行到左子树之前就访问）。切换中序 / 前序开关，注意看
visit(curr) 那一句在代码里从哪一行挪到哪一行，以及输出序列怎么随之改变。后序 (postorder) 也能用 Morris，但明显复杂：它在拆线索时不能简单访问单个节点，而要把刚走完的那条右脊逆序输出 ()，这需要一次链表反转；且根自身的整条右脊还得靠一个虚拟 dummy 根才能被统一输出（本页把它显式写成收尾一步）。切到上面的后序开关单步看：紫色高亮的就是当前被反转、逆序输出的那条右链。
3 · O(1) 空间从哪来：隐式的栈
Morris 看似没有用栈，但它并非凭空省下了空间——而是把栈分散藏进了树本来为 null 的指针位。
显式栈遍历里，栈保存的是「待回溯的祖先」。Morris 没有开数组，但它把「待回溯的祖先」这个信息，编码进了左子树最右节点的 right 线索里：你顺着左子树走到底，那条线索就是「弹栈后该回到谁」。所以它不是没有栈，而是借用了原本闲置的 null 指针位当栈，用完即还。这正是 O(1) 的来源——全程没有新开任何与树规模相关的内存。
3.1 · 时间仍是 O(n)：每条边最多走两次
内层「找最右节点」的循环看着像让总复杂度变成 O(n²)，其实不会。每个有左子树的节点，它到中序前驱的那条右链总共只被完整走两趟——一趟去装线索，一趟回来拆线索。每条树边被经过的次数是常数级，边数为 n − 1，所以总时间仍是 O(n)。
3.2 · 代价：遍历过程中树是「脏」的
省下 O(1) 空间不是没有代价。装线索的那一刻，树结构被临时改写（right 指向了祖先，破坏了「right 一定指向子节点」的不变量）：
- 不可重入 / 非线程安全：遍历途中若有别的线程读这棵树，会看到错误结构；中途异常退出会留下没拆的线索，树就坏了。
- 要求节点可写：必须能修改 right 指针，只读的树（如持久化 / 不可变结构）用不了 Morris。
| 方式 | 额外空间 | 时间 | 是否改树 | 特点 |
|---|---|---|---|---|
| 递归 | O(h) 调用栈 | O(n) | 否 | 最易写，深树有爆栈风险 |
| 显式栈迭代 | O(h) | O(n) | 否 | 最常用，控制力强 |
| Morris | O(1) | O(n) | 是 （临时） | 省空间，代价是改树 / 不可重入 |
什么时候真的该用 Morris? 绝大多数场景，递归或显式栈已经足够好、且更易读。Morris 的价值在内存极度受限、或题目明确要求 O(1) 额外空间时（典型如 LeetCode「二叉树中序遍历」的进阶要求）。把它当成一个理解「指针能当临时存储」的漂亮例子，比当成默认遍历方式更合适。