Morris遍历能省掉栈空间，是因为它复用二叉树中空闲的右指针临时构建回溯线索（即“穿线”），遍历完成后立即恢复原结构，仅需O(1)额外空间（几个指针变量）；其核心是动态建立并拆除前驱节点到当前节点的临时连接，不依赖递归栈或显式栈。
为什么Morris遍历能省掉栈空间？
Morris中序遍历的核心是“临时篡改右指针”，把原本空的 right 指针临时用作线索（thread），指向中序后继节点。遍历完再恢复原结构，所以不需要额外栈或递归调用栈 —— 空间复杂度真正压到 O(1)（仅用几个指针变量）。
关键前提：二叉树节点不带 parent 指针，且你**不能修改节点定义**（即不能加 flag 字段）。Morris 就是在这个约束下“借道而行”的解法。
容易踩的坑：
- 忘记恢复 right 指针，导致后续遍历错乱或重复访问
- 把“当前节点无左子树”和“左子树最右节点的 right 已指向当前节点”两种情况逻辑写反
- 在恢复指针后，错误地再次进入左子树（应统一走 current = current->right）
如何写出健壮的Morris中序循环体？
主干逻辑只有两个分支，但每步都要明确“现在在干什么”和“下一步去哪”。建议按以下顺序组织判断：
- 若
current->left == nullptr：直接输出current->val，然后跳向current->right - 否则，找左子树的“最右节点”（即中序前驱的右子树尽头）：
• 若其right == nullptr→ 建线索：predecessor->right = current，然后current = current->left
• 若其right == current→ 说明已回溯过左子树，此时恢复：predecessor->right = nullptr，输出current->val，再current = current->right
注意：找 predecessor 的过程必须用 while (predecessor->right && predecessor->right != current)，不能只写 while (predecessor->right)，否则会跳过已建好的线索。
遇到空树或单节点怎么不出错？
Morris 循环天然兼容边界情况，只要初始化正确就不会崩溃：
- 空树：初始
current = root为nullptr，循环直接不进，安全退出 - 单节点：
current->left == nullptr成立 → 输出值 →current = current->right（即nullptr）→ 循环结束 - 左倾/右倾链表：虽然时间退化到
O(n²)（每次找 predecessor 都要从头扫），但空间仍是O(1)；实际工程中极少出现，无需特殊处理
真正要检查的是指针解引用前是否为空 —— 所有 ->left、->right 访问前，都应确保 current != nullptr。循环条件写成 while (current) 即可兜底。
和递归/迭代中序对比时要注意什么？
Morris 输出顺序完全一致，但执行时机不同：它在“第二次抵达某节点时”才输出（即恢复线索后），而递归是在左子树返回后立即输出。这点在需要边遍历边修改树结构时尤其关键。
- 性能：Morris 时间平均
O(n)（每个边最多被访问 2 次），但常数因子比迭代大；适合内存极度受限场景（如嵌入式、刷题空间限制） - 副作用：会短暂改变树结构 —— 如果遍历中途被中断（如抛异常、信号打断），树可能处于损坏状态；生产环境慎用于共享数据结构
- 调试困难：无法像递归那样靠调用栈看路径，出错时需重点检查 predecessor 查找逻辑和指针恢复位置
最易忽略的一点：Morris 中序的“当前节点”在循环末尾总是走向 right，哪怕刚输出完一个节点 —— 这个统一跳转动作是保持逻辑收敛的关键，不要在输出后擅自改成 left 或其他分支。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
