morris前序遍历的核心思想是利用叶子节点空右指针建立临时线索，以o(1)额外空间实现遍历，且必须在首次抵达节点时立即访问并保证树结构最终复原。
Morris前序遍历的核心思想是什么？
它靠临时修改树结构（利用叶子节点的空右指针）建立线索，遍历完再复原。关键不是“不使用栈”，而是**用 O(1) 额外空间换空间复杂度，但必须保证树结构最终不变**。这意味着每条线索只能用一次、用完立刻断开。
和中序不同，前序需要在「第一次到达某节点时就访问」，而 Morris 中天然能捕获这个时机：当某个节点 cur 的左子树为空，或其左子树最右节点的 right 指向 cur（即已建立过线索），说明这是首次抵达——此时访问 cur 是安全且正确的。
如何判断是否该访问当前节点？
访问时机由 cur->left 是否为空，以及线索是否已存在共同决定：
- 如果
cur->left == nullptr，直接访问cur，然后去cur->right - 否则，找
cur左子树的最右节点（记为pre）：- 若
pre->right == nullptr：说明还没建过线索 → 访问cur（这是首次到达！），再让pre->right = cur，进入cur->left - 若
pre->right == cur：说明线索已存在 → 断开线索（pre->right = nullptr），然后去cur->right
- 若
注意：前序必须在建立线索前就访问 cur；中序是在线索断开后才访问。这点极易混淆，错放访问位置会导致重复或漏访问。
为什么不能直接复用中序 Morris 的代码改访问顺序？
因为线索建立与访问的耦合关系变了。中序访问发生在「从左子树返回时」（即第二次遇到 cur），而前序必须在「刚抵达 cur 且尚未深入左子树时」访问。若把中序的访问语句挪到建立线索前，会漏掉那些没有左子树的节点的后续右子树路径——因为一旦访问完就跳去 cur->left，而 cur->left 是 nullptr，接着又跳去 cur->right，逻辑看似通，但实际在找 pre 过程中可能已破坏了未访问分支的连接。
典型错误写法：
if (pre->right == nullptr) {
visit(cur); // ❌ 错！此时 cur->left 非空，但 cur 右子树还没被考虑
pre->right = cur;
cur = cur->left;
}
正确做法是：只要 cur->left 为空，就访问并走右；否则，在找 pre 前先访问（因这是首次抵达），再建线索走左。
完整可运行的 C++ 实现要点
需严格维护三件事：访问时机、线索建立/拆除、指针推进。下面是最简健壮版本的关键骨架：
void morrisPreorder(TreeNode* root) {
TreeNode* cur = root;
while (cur) {
if (!cur->left) {
visit(cur);
cur = cur->right;
} else {
TreeNode* pre = cur->left;
while (pre->right && pre->right != cur) {
pre = pre->right;
}
if (!pre->right) {
visit(cur); // ✅ 第一次到 cur，立即访问
pre->right = cur;
cur = cur->left;
} else {
pre->right = nullptr;
cur = cur->right;
}
}
}
}
注意：visit() 是你自己的处理逻辑（比如打印值）；TreeNode 假设含 val、left、right 成员；所有指针操作都基于原始树结构，无 new/delete。
容易被忽略的是边界：空树要直接 return；pre->right == cur 判断必须放在 pre->right != nullptr 之后，否则空指针解引用；还有，cur = cur->right 在两种分支下都要有，否则循环卡死。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
