Morris中序遍历实现O(1)额外空间，因其仅用cur、pre等常数个指针变量，复用节点空right指针临时建线索并立即恢复，不依赖栈或递归，所有操作均在原树结构上可逆完成。
为什么 Morris 中序遍历能实现 O(1) 额外空间？
因为整个过程不依赖栈或递归调用栈，只复用二叉树中原本为空的 right 指针（对左子树的叶子节点）临时构建线索，遍历完立即还原。关键不是“不修改树”，而是“修改可逆、且仅发生在空指针上”。真实内存占用只有几个指针变量：cur、pre、morris，与树规模无关。
核心逻辑：两次访问节点的判定条件怎么写？
节点被访问当且仅当它的左子树为空，或者其左子树的最右节点的 right 指针已指向它（即已被线索化过）。这对应两个分支：
- 若
cur->left == nullptr：直接输出cur->val，然后cur = cur->right - 否则找
cur左子树的最右节点pre：- 若
pre->right == nullptr：建立线索pre->right = cur，cur = cur->left - 若
pre->right == cur：说明左子树已遍历完，恢复树结构pre->right = nullptr，输出cur->val，再cur = cur->right
- 若
常见错误：线索未清除或判断错位导致死循环
典型现象是程序卡在某个节点反复跳转，或输出重复值。根本原因常是以下之一：
- 忘记在第二次访问时将
pre->right置为nullptr，导致后续再次误判为“已线索化” - 找
pre时循环条件写成pre->right != nullptr，漏掉pre->right == cur的情况，导致永远进不去恢复分支 - 初始
cur设为root是对的，但误在cur == nullptr时提前退出，而实际应以cur != nullptr为循环条件
正确循环头应为：
while (cur != nullptr) { ... }
立即学习“C++免费学习笔记（深入）”；
C++ 实现中指针操作的边界安全要点
所有指针解引用前必须确认非空，尤其在找 pre 时：
- 进入
while (pre->right != nullptr && pre->right != cur)前，先确保pre != nullptr（由cur->left非空保证） - 内层循环中，每次移动
pre后都要检查pre->right是否为空，避免野指针 - 不要假设
TreeNode的right初始一定为nullptr—— 若树由其他算法构造并残留了脏指针，Morris 过程会崩溃；生产环境建议加断言：assert(pre->right == nullptr || pre->right == cur);
空间复杂度的数学本质就在这里：你无法用更少的变量来跟踪当前路径——cur 定位当前节点，pre 用于查找，二者缺一不可；任何试图合并它们的尝试都会破坏状态机的确定性。
