Morris前序遍历的核心判断逻辑在于访问时机：必须在cur->left==nullptr时立即访问cur，或在找到左子树最右节点prev且prev->right==nullptr（首次到达）时立即访问cur并建链；绝不能在prev->right==cur时访问——那是中序位置，否则将导致漏访、重复或乱序。
Morris前序遍历的核心判断逻辑在哪
关键不在“怎么走”，而在“什么时候访问节点”——Morris 前序必须在建立线索时立即访问当前节点，而不是等回溯。一旦搞反顺序（比如像中序那样等回到左子树最右节点再访问），结果就全错。
典型错误现象：root 被漏访、节点重复访问、输出序列乱序（如本该是 1 2 3 却变成 2 1 3）。
- 访问时机只发生在两种情况：
cur->left == nullptr时直接访问cur；或找到cur左子树的最右节点prev后，若prev->right == nullptr（即首次到达），立刻访问cur，再把prev->right指向cur - 绝不能在
prev->right == cur（即第二次到达）时访问cur——那是中序的位置 - 每次访问后都要推进
cur = cur->right，哪怕刚建完线索，否则会卡死在原地
如何安全复位线索不破坏树结构
复位不是可选项，是必须动作：所有被临时修改的 right 指针（即指向祖先的线索）都得在离开该子树前清空，否则后续遍历或调试时看到的树是脏的。
常见疏忽：只在 prev->right == cur 分支里恢复 prev->right = nullptr，却忘了在 cur->left == nullptr 的分支里，cur 本身可能就是某个更早线索的目标，但它没被“动过”，所以无需复位——这点容易想多。
立即学习“C++免费学习笔记（深入）”；
- 仅当
prev->right == cur成立时，说明这条线索已被用过一次，此时必须执行prev->right = nullptr - 复位后，才允许执行
cur = cur->right，否则会跳过右子树 - 如果树原本就含
right指向非空但非线索的指针（比如自定义结构体混用），Morris不适用——它默认right字段完全可控
C++实现中指针操作的三个易崩点
不是语法错，而是边界条件引发的段错误或无限循环，90% 都出在这三处：
-
prev = cur->left后没判prev != nullptr就直接进 while 循环，导致对空指针取->right - while 循环内写成
while (prev->right)，漏掉prev->right != cur判断，结果把已建好的线索当成新路径反复绕圈 - 在
cur->left == nullptr分支里访问完cur后，写成cur = cur->left（错！应为cur = cur->right），导致直接坠入空指针
正确骨架节选：
while (cur) {
if (!cur->left) {
visit(cur); // 立即访问
cur = cur->right; // 注意：不是 left
} else {
auto prev = cur->left;
while (prev->right && prev->right != cur) {
prev = prev->right;
}
if (!prev->right) {
visit(cur); // 第一次到，立即访问
prev->right = cur;
cur = cur->left;
} else {
prev->right = nullptr; // 复位
cur = cur->right;
}
}
}为什么 Morris 前序不适合带 parent 指针的树
因为 Morris 的本质是用 right 字段模拟栈行为，而 parent 指针的存在让树结构不再“干净”——你无法区分某个 right 是用户数据、还是你临时写的线索。
更实际的问题：如果你的节点结构是 struct Node { Node* left; Node* right; Node* parent; };，那么 prev->right = cur 这一操作虽然语法合法，但会覆盖掉原本可能有效的 parent 关系（如果设计上 right 和 parent 共享语义），后续调试器看树会彻底混乱。
- 标准
Morris假设节点只有left/right两个指针，且无其他逻辑绑定 - 若真需要 parent 支持，宁可用栈模拟（O(h) 空间），别硬套
Morris - 面试中若被问“能否扩展支持 parent”，直接说：可以，但要额外字段标记线索状态，那就失去零空间意义了
真正难的不是写对代码，是记住“访问必须前置”和“复位不可省略”这两条铁律。一旦在复杂嵌套场景里漏掉某次复位，bug 会藏得很深——它可能只在特定形状的树（比如左倾链）上触发，而且只影响部分节点。
