什么是 Morris 遍历？为什么它能做到 O(1) 额外空间？

简化版

Morris 遍历利用空闲的右指针临时建立“前驱节点到当前节点”的线索，从而不用递归栈或显式栈完成遍历。中序遍历时，若当前节点有左子树，就找到左子树最右节点作为前驱，建立或拆除线索；时间 O(n)，额外空间 O(1)。

详细版

中序 Morris 的规则是：当前节点没有左子树，直接访问并走右边；有左子树时，找当前节点的中序前驱 pre。如果 pre.right == null，说明第一次到当前节点，建立 pre.right = cur 并转向左子树；如果 pre.right == cur，说明左子树已经访问完，拆线索、访问当前节点、转向右子树。

List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            ans.add(cur.val);
            cur = cur.right;
        } else {
            TreeNode pre = cur.left;
            while (pre.right != null && pre.right != cur) pre = pre.right;
            if (pre.right == null) {
                pre.right = cur;
                cur = cur.left;
            } else {
                pre.right = null;
                ans.add(cur.val);
                cur = cur.right;
            }
        }
    }
    return ans;
}

Morris 会临时修改树结构，所以必须在线索第二次遇到时恢复。

完整版教学

一、普通遍历为什么需要额外空间

递归遍历看似没有显式数据结构，但调用栈保存了“访问完左子树后要回到哪个节点”。迭代遍历则用栈显式保存这批返回点。Morris 的目标就是不使用这些栈空间，改用树上原本为空的指针临时记录返回路径。

递归栈保存: 左子树访问完 -> 回到当前节点
Morris 保存: 前驱.right -> 当前节点

它不是改变遍历顺序，而是把“回来的路”临时写到树里。遍历结束后再把这些临时指针恢复为空。

二、中序前驱为什么能带你回来

在中序遍历中，当前节点 cur 的访问顺序是：左子树全部节点，然后 cur，然后右子树。左子树中最后被访问的节点，就是当前节点的中序前驱，也就是左子树一路向右走到的最右节点。让这个前驱的 right 临时指向 cur，就能在左子树访问完后回到 cur。

      cur
     /
   left
      \
      pre

建立线索: pre.right = cur

因为 pre 原本是左子树最右节点，它的右指针在普通二叉树中应为空。这个空位正好可以临时存线索。

三、两次遇到前驱分别代表什么

找到前驱 pre 后，如果 pre.right == null，说明还没进入左子树，需要建立线索并向左走。如果 pre.right == cur，说明这是通过线索第二次回到 cur，左子树已经处理完，应该拆掉线索并访问 cur。

条件	含义	动作
`pre.right == null`	第一次到 cur	建线索，去左子树
`pre.right == cur`	左子树已完成	拆线索，访问 cur，去右子树
`cur.left == null`	没有左子树	直接访问 cur

这张表是 Morris 中序的核心，只要记住它，代码不会乱。

四、为什么总时间仍然是 O(n)

看起来每个节点都可能去左子树找最右节点，似乎会重复很多次。但每条临时线索最多建立一次、拆除一次，每条边也只会被有限次经过。整体访问和指针检查次数与节点数成线性关系，所以时间复杂度是 O(n)。

每个节点:
作为 cur 被处理若干常数次
作为 pre 的右线索最多建立 1 次、拆除 1 次
总计仍是线性

额外空间 O(1) 指的是不使用递归栈和显式栈；输出列表如果算入结果空间，当然是 O(n)。

五、前序和后序 Morris 的变化

前序 Morris 和中序很像，只是访问当前节点的时机提前：第一次建立线索时访问 cur，因为前序是根、左、右。后序 Morris 更复杂，通常需要引入虚拟头节点，并在拆线索时逆序访问某段右边界。面试中若只问 Morris，先把中序讲透最重要。

中序: 第二次回到 cur 时访问
前序: 第一次到 cur 时访问
后序: 拆线索时处理边界逆序

如果岗位不是算法强相关，能准确说出中序 Morris 的机制和恢复指针，通常已经足够。

六、常见误区与追问

记忆钩子：Morris 的本质是“借空右指针当回程票”，用完必须归还。

误区：Morris 完全不修改树。 它会临时修改右指针，只是遍历结束前必须恢复。
误区：找到前驱后总是访问当前节点。 中序要等第二次通过线索回来时才访问当前节点。
误区：Morris 适合所有场景。 如果树结构不能被临时修改，或遍历中可能被并发读取，就不适合。
追问：为什么空间是 O(1)？ 它只用几个指针变量，没有递归栈和显式栈。
追问：如何避免死循环？ 找前驱时条件必须是 pre.right != null && pre.right != cur，第二次遇到要拆线索。
追问：前序 Morris 和中序区别？ 前序在第一次建立线索时访问当前节点，中序在拆线索时访问。

七、加强记忆

Morris 遍历可以记成“线索化临时回家路”。普通递归靠栈记住从左子树回来后访问谁，Morris 靠前驱节点的空右指针记住这个返回点。第一次见前驱就建线索，第二次见前驱就拆线索并继续，这样既不丢路，也能在结束时把树恢复原样。

简化版

详细版