morris前序遍历通过复用空闲右指针构建线索实现o(1)空间复杂度：首次访问节点即输出，有左子树则建线索后向左，第二次返回时拆线索并向右；需严格判空防护与双阶段验证确保正确性。
如果您尝试在不使用栈或递归的情况下实现二叉树的前序遍历，则Morris遍历提供了一种仅用常数额外空间的解决方案。以下是该算法的深度解析与具体实现步骤：
一、Morris前序遍历核心逻辑
Morris前序遍历通过临时复用节点空闲的右指针构建回溯线索，遍历完成后恢复原始结构，从而实现O(1)空间复杂度。其关键在于访问时机必须前置：每次首次抵达某节点时立即访问该节点值；若节点无左子树，则直接访问后向右移动；若存在左子树，则先访问当前节点，再建立指向自身的线索，随后进入左子树；当第二次沿线索返回时，拆除线索并转向右子树。
1、初始化当前节点指针 curr 指向根节点。
2、当 curr 不为空时，执行后续判断。
3、若 curr->left == nullptr，则将 curr->val 加入结果容器，并令 curr = curr->right。
4、若 curr->left != nullptr，则声明指针 pred 指向 curr->left。
5、执行循环：while (pred->right != nullptr && pred->right != curr)，使 pred 移动至其左子树最右节点。
6、若此时 pred->right == nullptr，则将 curr->val 加入结果容器，设置 pred->right = curr，再令 curr = curr->left。
7、若此时 pred->right == curr，则将 pred->right 置为 nullptr 以恢复树结构，并令 curr = curr->right。
二、C++代码实现中的边界防护策略
为避免空指针解引用与无限循环等常见崩溃，需在关键操作前插入显式判空检查。所有指针移动与赋值均须确保目标非空，且线索建立与拆除必须严格配对。该策略不增加辅助空间，仅强化原生指针操作的安全性。
1、在进入左子树查找前，先判断 curr->left 是否为空，否则跳过整个pred查找流程。
2、在执行 pred->right 赋值前，确认 pred 非空。
3、在将 curr 更新为 curr->left 或 curr->right 前，确保对应子节点指针合法。
4、循环终止条件必须同时包含 curr != nullptr 与子节点判空分支，防止因单一分支遗漏导致死循环。
三、双阶段验证法保障输出正确性
该方法通过两次独立遍历验证Morris前序结果是否与标准递归前序一致：第一阶段生成Morris结果序列；第二阶段在不修改树结构前提下运行递归前序作为黄金标准；最后逐元素比对两序列。此过程虽不嵌入主算法，但可作为调试阶段强制启用的校验机制，确保线索操作未引发隐式结构破坏。
1、定义辅助函数 recursivePreorder(TreeNode* node, vector
2、在主函数末尾调用该函数，传入原始 root 与空结果容器 ref_result。
3、使用 std::equal 对比 morris_result 与 ref_result 的内容。
4、若比对失败，抛出异常并输出首个差异索引位置，便于定位线索建立/拆除错误点。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
