Morris中序遍历实现O(1)额外空间，因其复用树节点right指针临时存储回溯信息，通过找前驱、建线索、恢复并右移三步完成遍历，所有修改均成对可逆，不申请新内存。
为什么 Morris 中序遍历能实现 O(1) 额外空间？
因为它根本不用栈或递归调用栈，也不建临时节点——所有“回溯”信息都复用二叉树本身的 right 指针临时存储。关键在于：对每个有左子树的节点 cur，先找到它的中序前驱（即左子树最右节点），然后把前驱的 right 指向 cur，形成一条向上的“线索”。等左子树处理完，再顺着这条线索回来，同时恢复原树结构。
这个过程不申请任何新内存，只改指针、再改回来，所以额外空间恒为常数。注意：这不是“不修改树”，而是“修改后必恢复”，这是 O(1) 空间的前提。
核心逻辑三步走：找前驱、建线索、恢复并右移
实际写代码时，不能只套模板，得盯住三个分支的流转条件：
- 当
cur->left == nullptr：直接输出cur->val，然后cur = cur->right - 当
cur->left != nullptr，先找前驱：pred = cur->left，一路pred->right到底（但要跳过已建好的线索）；如果pred->right == nullptr，说明第一次来，建线索pred->right = cur，然后cur = cur->left - 如果
pred->right == cur，说明左子树已处理完，此时恢复pred->right = nullptr，输出cur->val，再cur = cur->right
漏掉恢复步骤会导致树结构永久损坏；错判 pred->right 是 nullptr 还是 cur 会陷入死循环。
常见错误：空指针、无限循环、输出顺序错乱
这些基本都出在前驱查找和线索判断上：
- 找前驱时没加
pred->right != cur的终止条件，导致绕线索兜圈 → 死循环 - 恢复线索后忘了置
pred->right = nullptr，下次再进同一分支会误判 → 输出重复或跳过节点 - 在
cur->left == nullptr分支里输出后直接cur = cur->right，但没考虑cur可能是叶子节点 → 没问题；真正危险的是在建线索分支里漏了continue或提前右移，导致重复访问 - 用
int存值但节点值可能为INT_MIN，若用标记值代替指针判断（比如用val == -1表示线索），会崩溃 → 必须用指针比较，别魔改数据域
C++ 实现要点：指针操作必须显式、安全、可逆
标准实现不依赖智能指针，用裸指针即可，但每处修改都要有对应还原：
while (cur != nullptr) {
if (cur->left == nullptr) {
result.push_back(cur->val);
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; // 恢复
result.push_back(cur->val);
cur = cur->right;
}
}
}
注意：循环内 cur 的更新路径有且仅有三处，每处目的清晰；pred->right != cur 是防止自己指向自己的死循环；所有指针赋值都无条件可逆——这才是空间复杂度严格 O(1) 的工程保障。
真正难的不是写出来，而是在多层嵌套、空节点、单边树等边界下，仍保证线索建立/拆除的原子性和对称性。一旦某个 pred->right 被设为 cur 却没恢复，整棵树就不可逆污染了。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
