morris前序遍历的核心判断条件是：当前节点左子树为空时直接访问并右移；否则找左子树最右节点，若其右指针为空则建线索、访问当前节点、进入左子树，若指向当前节点则断开线索并右移。
Morris前序遍历的核心判断条件是什么？
Morris前序遍历不靠栈或递归，靠临时修改树的空右指针建立线索，遍历完再还原。关键在于：每次访问节点的时机必须严格对应“该节点第一次被抵达”且“左子树已处理完毕”的状态。
- 当前节点
cur的左子树为空 → 直接访问cur，然后跳到cur->right - 否则，先找左子树的最右节点（即中序前驱）：
- 若其
right为空 → 建线索：pred->right = cur，访问cur，进入左子树（cur = cur->left） - 若其
right == cur→ 说明左子树已遍历完，断开线索：pred->right = nullptr，然后跳向cur->right
- 若其
注意：访问 cur 必须放在“建线索后、进左子树前”，这是前序和中序的根本区别（中序是断开线索后才访问）。
为什么不能在断开线索时再访问根节点？
那样会变成中序行为。前序要求“根 → 左 → 右”，所以根必须在深入左子树前就输出。
- 错误写法（类中序）：
if (pred->right == cur) { pred->right = nullptr; visit(cur); cur = cur->right; } - 正确逻辑（前序）：
if (pred->right == nullptr) { visit(cur); pred->right = cur; cur = cur->left; } else { pred->right = nullptr; cur = cur->right; }
常见坑：把 visit(cur) 放在 else 分支里，结果输出顺序变成左子树优先，完全偏离前序定义。
如何安全还原树结构且不漏节点？
Morris 算法的“零辅助空间”代价是临时改指针，还原依赖两个守恒点：
- 每个线索只建一次、只拆一次
- 所有
right指针最终必须恢复为原始值（nullptr或原右子节点）
确保还原的关键操作：
-
pred必须严格定义为“cur左子树中最右节点”，不能用while (pred->right)无条件走到底（可能走入已建的线索环） - 正确找前驱：
TreeNode* pred = cur->left; while (pred->right && pred->right != cur) pred = pred->right;
- 只有当
pred->right == nullptr时才建线索；只有当pred->right == cur时才拆线索并右移
漏还原的典型现象：多次运行同一棵树，第二次开始出现无限循环 —— 因为上一轮的线索没清干净。
C++实现中容易忽略的空指针与边界处理
-
cur 初始为 root，但 root 可能为 nullptr，需开头判空
- 找前驱时，
cur->left 可能为空，此时整个 while 不执行，pred 未初始化 → 必须显式初始化为 nullptr 或直接跳过
- 访问节点逻辑不能耦合在指针移动之后，否则
cur 变为 nullptr 时还试图 visit(cur)
cur 初始为 root，但 root 可能为 nullptr，需开头判空cur->left 可能为空，此时整个 while 不执行，pred 未初始化 → 必须显式初始化为 nullptr 或直接跳过cur 变为 nullptr 时还试图 visit(cur)
推荐主循环结构：
while (cur) { if (!cur->left) { visit(cur); cur = cur->right; } else { /* 找pred，按线索状态分支 */ } }
真正难的不是逻辑推导，而是每一步指针修改都得同时满足：不破坏后续查找路径、不提前释放线索、不重复访问。稍一错位，要么死循环，要么漏节点，要么改坏原树。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
