Morris前序遍历需分两类节点处理：无左子树则直接访问并右移；有左子树则找前驱，首次抵达时访问并建线索后左移，第二次抵达时恢复结构后右移，严禁统一延迟访问。
Morris前序遍历的核心判断逻辑
Morris前序遍历能省掉栈和递归，关键在于利用叶子节点的空右指针“临时搭桥”回溯。但必须严格区分两种节点：有左子树的节点要先线索化再访问，没左子树的节点直接访问——**不是所有节点都按“访问→向右”走，这是初学者最常写错的地方**。
典型错误是把 root->left == nullptr 和 “当前已建立好前驱线索” 混为一谈，结果重复访问或跳过节点。正确做法是：每次进入循环，先检查是否有左子树；没有就直接访问并走向右；有则找前驱，再决定是建线索还是恢复结构并访问。
如何安全地找前驱并避免死循环
前驱是左子树的最右节点，但要注意它可能已经被连过一次（即 pred->right == root），此时说明左子树已遍历完，该访问当前节点了。否则才建立线索。
- 找前驱时，用
while (pred->right && pred->right != root)，不能只写pred->right，否则会误入已建好的线索导致无限循环 - 建立线索后，必须立刻
root = root->left，不能在原地继续判断，否则会反复建同一条线索 - 恢复结构时（即
pred->right == root分支），要把pred->right置为nullptr，否则后续中序/后序复用该树时会出错
前序访问时机与顺序陷阱
前序要求“根→左→右”，而 Morris 的线索机制天然适合在第一次抵达某节点时做操作。所以访问必须放在两个位置：无左子树时立即访问，有左子树且前驱已连好（即第二次抵达）时，在恢复结构后访问。
常见错误是把访问统一放在“找到前驱之后”，这会导致根节点被延迟到左子树遍历完才输出，变成变相的中序。
正确片段示意：
if (root->left == nullptr) {
result.push_back(root->val); // ← 这里访问
root = root->right;
} else {
TreeNode* pred = root->left;
while (pred->right && pred->right != root) pred = pred->right;
if (pred->right == nullptr) {
result.push_back(root->val); // ← 这里也访问（第一次抵达）
pred->right = root;
root = root->left;
} else {
pred->right = nullptr; // 恢复
root = root->right; // 不再访问 root，它已输出过了
}
}
边界与多线程下的注意事项
Morris 算法会临时修改树结构，这意味着它不是线程安全的，也不能和其它遍历（比如正在运行的中序迭代器）共存。生产环境若需并发，要么加锁，要么改用带栈版本。
另外，空树、单节点、只有左/右链的树都要验证。特别注意：当 root 为 nullptr 时，循环体不能执行任何解引用；而右斜树（每个节点只有右子）会退化为普通链表遍历，此时完全不触发线索逻辑，纯靠 root = root->right 推进——这点容易被测试遗漏。
真正难的不是写出循环，而是确保每条路径上的访问顺序、指针修复、空指针防护三者同时成立。实际调试时，建议用三节点树（根+左+右）手推两轮，比跑十次自动化测试更能暴露时机错误。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
