Morris遍历的核心思想是利用二叉树中空闲的右指针临时建立线索，指向中序后继节点，遍历完成后恢复原结构，实现O(1)空间复杂度；其关键操作包括找左子树最右节点、判断并建立/拆除线索、按需访问节点。
Morris遍历的核心思想：用空指针“借道”做线索
Morris遍历不是靠栈或递归，而是临时修改二叉树结构，把原本指向 null 的右指针（对左子树而言）或左指针（对右子树而言）重定向为“线索”，指向中序/前序的后继节点。遍历完再恢复原状——空间复杂度真正压到 O(1)，连函数调用栈都不用（非递归版需显式栈，递归版隐式栈仍是 O(h)）。
关键前提：所有节点的 right 指针在初始时都可能为空；我们只利用这些“闲置”指针临时建立线索，且保证每条线索最多被使用两次（建立 + 拆除），不会漏节点、不破坏逻辑顺序。
中序遍历的Morris实现：三步循环 + 一次回溯
核心是找当前节点 cur 的前驱（inorder predecessor）：即左子树最右节点。如果前驱的 right 是空，就把它指向 cur，然后向左走；如果已指向 cur，说明左子树已处理完，输出 cur->val，断开线索，向右走。
- 每次进入左子树前，必须先找前驱：用
pred = cur->left，再循环while (pred->right && pred->right != cur) pred = pred->right - 若
pred->right == nullptr：建立线索pred->right = cur，cur = cur->left - 若
pred->right == cur：恢复结构pred->right = nullptr，访问cur，cur = cur->right - 注意边界：当
cur为nullptr时循环结束，无需额外判空入口
示例片段（中序）：
立即学习“C++免费学习笔记（深入）”；
while (cur) {
if (!cur->left) {
res.push_back(cur->val);
cur = cur->right;
} else {
TreeNode* pred = cur->left;
while (pred->right && pred->right != cur) pred = pred->right;
if (!pred->right) {
pred->right = cur;
cur = cur->left;
} else {
pred->right = nullptr;
res.push_back(cur->val);
cur = cur->right;
}
}
}前序遍历只需微调访问时机，但不能直接套用中序逻辑
中序是“左→根→右”，访问发生在从左子树返回时；前序是“根→左→右”，访问必须在第一次抵达节点时发生——也就是建立线索前，或发现无左子树时。
- 当
cur->left == nullptr：直接访问cur，再向右 - 当有左子树且前驱的
right为空：此时是第一次来，立刻访问cur，再建线索、向左 - 当有左子树且前驱的
right == cur：说明左子树已遍历完，直接向右，**不再访问cur**（否则会重复） - 常见错误：把访问统一放在
else分支末尾，导致根节点被漏掉或重复
所以前序的访问点只有两个：无左子树时、有左子树且首次抵达时。
后序遍历无法直接 Morris，但可用“翻转右路径”技巧模拟
Morris 本身不支持自然的后序（左→右→根），因为线索只提供单向回溯能力。但可以复用中序的线索构造过程，配合局部链表反转实现：每当从某节点沿右指针回溯时，把这一段路径（从该节点到前驱）的指针全部反转，访问后再反转回来。
- 仅在
pred->right == cur分支中触发：此时从cur到pred构成一条临时右斜路径 - 用标准链表反转（三指针）遍历这条路径并收集节点值，最后再反转还原指针
- 注意：反转的是“当前节点到前驱”的右链，不是整棵树；且反转后要记得恢复，否则树结构永久损坏
- 性能上多了一次路径扫描，但仍是
O(n)时间、O(1)空间
这个技巧容易被忽略：后序的 Morris 不是“改一改条件就行”，而必须引入额外的链表操作，且极易因反转/恢复不匹配导致段错误或无限循环。
真正难的不是写通代码，而是确保每次线索建立和拆除都严格配对，尤其在含空子树、单边树、退化为链表等边界情况下。哪怕漏一个 pred->right = nullptr，下一轮遍历就会走入野指针——Morris 的简洁是以对指针操作的绝对精确为代价的。
