Morris中序遍历以O(1)额外空间实现，核心是利用左子树最右节点的空右指针临时链接回当前节点；访问时若无左子树则直接输出并右移，否则找前驱、打链（未打过）或还原+输出+右移（已打过），必须配对还原右指针以保树结构。
Morris中序遍历的核心思想是用叶子节点的空右指针“临时链接”回祖先，避免递归栈或显式栈
它不新建任何容器，也不递归，真正实现 O(1) 额外空间（除输出结果外）。关键在于：当访问到某个节点 cur 时，如果它没有左子树，直接输出并走右；否则，先找到它的**左子树最右节点**（即中序前驱），把该前驱的右指针临时指向 cur，然后向左走——这步“打链”是可逆的，后续会还原。
如何判断是否已打过链？看左子树最右节点的右指针是否指向当前节点
这是 Morris 遍历最易错的逻辑分支。对每个 cur，先找其左子树的最右节点 pre（即 pre = cur->left; while (pre->right && pre->right != cur) pre = pre->right;）：
- 若
pre->right == nullptr：说明还没打链，执行pre->right = cur，然后cur = cur->left - 若
pre->right == cur：说明已打过链、现在是“回溯回来”，此时应恢复树结构（pre->right = nullptr），输出cur，再向右走（cur = cur->right）
C++ 实现中必须手动还原右指针，否则破坏原树结构
很多初学者只关注遍历顺序，忽略还原步骤，导致二次遍历出错或调试时树被改坏。注意以下几点：
- 所有对
pre->right的赋值都要配对还原（仅在pre->right == cur分支里还原） - 不能在
cur为nullptr时访问cur->left，循环条件应为cur != nullptr - 输出时机只在“回溯路径”上：即确认
pre->right == cur后、还原前 - 示例片段（非完整类，仅主干）：
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
TreeNode* cur = root;
while (cur) {
if (!cur->left) {
res.push_back(cur->val);
cur = cur->right;
} else {
TreeNode* pre = cur->left;
while (pre->right && pre->right != cur) pre = pre->right;
if (!pre->right) {
pre->right = cur;
cur = cur->left;
} else {
pre->right = nullptr; // 必须还原！
res.push_back(cur->val);
cur = cur->right;
}
}
}
return res;
}
与递归/栈版本对比：Morris 不支持中途 break，且无法自然获取父节点信息
如果你需要在遍历中根据条件提前退出（比如找第一个大于 x 的值），Morris 虽然能做，但逻辑会变复杂——因为“打链”和“还原”耦合在流程里，中断后可能留脏状态。另外，它完全不暴露调用栈或父指针，想在访问某节点时知道它是谁的左/右孩子，得额外记录（比如用哈希表缓存父子关系，但这破环了 O(1) 空间承诺）。
立即学习“C++免费学习笔记（深入）”；
真正节省空间的代价，是牺牲了遍历过程中的上下文可见性。写完别忘了跑个 nullptr 输入和单节点树验证边界——这两处最容易漏判空指针。
