Morris遍历能省栈和递归空间，因其复用树本身指针构建临时线索：将无右子树节点指向中序后继，访问后恢复原结构，全程仅用常数个指针变量，实现O(1)额外空间。
为什么Morris遍历能省掉栈和递归空间
Morris中序遍历的核心是“临时篡改右子节点指针，复用树结构本身做线索”，不额外申请栈帧或容器。它把每个没有右子树的节点，临时指向其**中序后继**（即当前节点在中序序列里的下一个节点），遍历完再恢复原结构。关键在于：所有指针操作都在原树上完成，TreeNode* 指针变量只用常数个，真正实现 O(1) 额外空间。
注意：这不是“不修改树”，而是“修改后必恢复”——这是它区别于破坏性遍历的关键。一旦中途退出（比如提前找到目标值），树可能处于中间态，必须小心处理。
怎么写一个安全可复用的Morris中序循环体
主干逻辑分两路：当 cur->left == nullptr 时直接访问并走右；否则找左子树最右节点（即 cur 的前驱），建立/拆除线索。重点在判断是否已访问过左子树——靠检查 predecessor->right == cur 是否成立。
- 若
predecessor->right == nullptr：说明左子树未访问，建立线索predecessor->right = cur，然后cur = cur->left - 若
predecessor->right == cur：说明左子树已回溯完毕，恢复树结构predecessor->right = nullptr，访问cur，再cur = cur->right
示例关键片段：
while (cur != nullptr) {
if (cur->left == nullptr) {
visit(cur); // 如 push_back 到结果 vector，或直接处理
cur = cur->right;
} else {
TreeNode* pred = cur->left;
while (pred->right != nullptr && pred->right != cur)
pred = pred->right;
if (pred->right == nullptr) {
pred->right = cur;
cur = cur->left;
} else {
pred->right = nullptr;
visit(cur);
cur = cur->right;
}
}
}
容易踩的坑：空指针、重复访问、提前退出后树损坏
Morris遍历对指针操作极度敏感，三个高频问题：
-
pred->right == nullptr判断前，必须先确保pred != nullptr，否则空指针解引用——尤其当cur->left是叶子时，pred就是它自己，但若树为空或cur为nullptr，需前置校验 - 访问节点位置必须严格在
pred->right == cur分支里（左子树已处理完）和cur->left == nullptr分支里（无左子树），漏掉任一分支会导致跳过节点或重复访问 - 如果在
visit()中提前return或抛异常，当前线索（如pred->right = cur）可能尚未恢复，后续再次遍历时会进入死循环或崩溃——务必把恢复逻辑（pred->right = nullptr）放在visit()前，或用 RAII 封装线索生命周期
C++实现中要不要用智能指针？会影响O(1)空间吗
不用。Morris遍历的空间复杂度分析对象是**算法执行期额外申请的动态内存**，而 std::unique_ptr 或 std::shared_ptr 本身要维护控制块、引用计数等，会引入隐式堆分配，破坏 O(1) 承诺。实际工程中，只要输入树由裸指针管理（常见于 LeetCode 风格题），就全程用 TreeNode*；若原始树用智能指针构建，应先提取裸指针视图，遍历完成后再丢弃——别让智能指针参与线索链接过程。
真正影响空间的是你是否在循环里 new 了任何东西，或者用了 std::stack、std::vector 存节点——这些全得砍掉。连结果存储（如返回 vector）都不算在算法空间复杂度里，那是输出成本，不是遍历开销。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
