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

常见错误：线索未清除或判断错位导致死循环

典型现象是程序卡在某个节点反复跳转，或输出重复值。根本原因常是以下之一：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

• 忘记在第二次访问时将 pre->right 置为 nullptr，导致后续再次误判为“已线索化”
• 找 pre 时循环条件写成 pre->right != nullptr，漏掉 pre->right == cur 的情况，导致永远进不去恢复分支
• 初始 cur 设为 root 是对的，但误在 cur == nullptr 时提前退出，而实际应以 cur != nullptr 为循环条件

正确循环头应为：

while (cur != nullptr) { ... }

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 用于查找，二者缺一不可；任何试图合并它们的尝试都会破坏状态机的确定性。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！