morris遍历是唯一能在不使用递归栈、显式栈或队列前提下实现o(1)空间复杂度的二叉树前序与后序遍历方法：前序在首次抵达节点时立即访问，后序则通过逆序输出左子树右边界并全局翻转来达成“左→右→根”顺序，二者均依赖临时复用空right指针建立/拆除线索，且需严格重置线索以防冲突。
如果您需要在不使用递归调用栈、也不借助显式辅助栈或队列的前提下完成二叉树的前序与后序遍历，则Morris遍历是唯一能达成O(1)空间复杂度的可行路径。以下是针对前序与后序两种遍历目标分别展开的零辅助空间实现方法：
一、Morris前序遍历：空左即访，建链前必访
Morris前序遍历要求每个节点在第一次抵达时立即访问，以确保“根→左→右”顺序不被破坏；其本质是利用左子树最右节点的空闲right指针临时建立回溯线索，并在第二次返回时清除该线索。关键约束在于：当cur->left为nullptr时必须直接访问并跳转至右子树，否则将遗漏该节点。
1、初始化当前节点cur为根节点；
2、进入while(cur != nullptr)循环；
3、若cur->left == nullptr：立即执行result.push_back(cur->val)，随后cur = cur->right；
4、若cur->left != nullptr：先执行result.push_back(cur->val)，再查找cur的前驱pred（即cur->left子树中最右节点）；
5、在查找pred过程中，使用while(pred->right != nullptr && pred->right != cur)迭代；
6、若pred->right == nullptr，则令pred->right = cur，然后cur = cur->left；
7、若pred->right == cur，则令pred->right = nullptr，然后cur = cur->right。
二、Morris后序遍历：逆右边界输出 + 全局翻转
Morris后序遍历无法像前序或中序那样单次线性访问，因其必须保证“左→右→根”的访问顺序，而Morris结构本身不支持自然回溯；标准解法是沿每次第二次抵达节点时的左子树最右路径进行逆序输出，再对整段输出做一次全局逆序，从而还原为真实后序序列。该过程必须严格维护tail != curr作为翻转终止条件，且恢复指针时需使用tail->right = prev而非其他赋值形式。
1、初始化cur为根节点，结果容器暂存逆后序序列；
2、进入while(cur != nullptr)循环；
3、若cur->left == nullptr，则cur = cur->right；
4、若cur->left != nullptr，查找前驱pred（同前序），但仅在pred->right == cur时触发处理分支；
5、当pred->right == cur时，令tail = cur->left，prev = nullptr；
6、执行子路径翻转：while(tail != curr) { TreeNode* next = tail->right; tail->right = prev; prev = tail; tail = next; }；
7、沿翻转后的链表从prev开始逆向访问并压入结果：while(tail != nullptr) { result.push_back(tail->val); TreeNode* next = tail->right; tail->right = prev; prev = tail; tail = next; }；
8、循环结束后，对result整体执行reverse(result.begin(), result.end())。
三、双遍历共用结构的安全重置方案
同一棵二叉树连续调用前序与后序Morris遍历极易引发指针冲突，因前序残留的临时线索会干扰后序的pred判断逻辑；必须在每次遍历前确保所有节点的right指针处于原始状态，即未被修改为指向任意cur节点。该重置不可依赖自动析构，而需主动扫描并清零所有非法right链接。
1、定义辅助函数clearMorrisLinks(TreeNode* root)，以深度优先方式遍历全树；
2、对每个非空节点node，检查其right是否指向树内某节点（可通过遍历验证是否构成环或超出地址范围）；
3、若node->right非nullptr且node->right不等于node->left、node->right->left、node->right->right中的任一合法子节点地址，则强制置node->right = nullptr；
4、递归处理node->left与node->right；
5、调用前序遍历前执行clearMorrisLinks(root)；
6、调用后序遍历前再次执行clearMorrisLinks(root)。
四、调试期关键指针状态观测法
在开发与调试阶段，仅靠输出结果难以定位Morris遍历中因线索未清除或误建导致的死循环、段错误等问题；必须在关键分支插入实时指针状态打印，尤其关注pred->right在不同阶段的实际取值，以区分“首次访问”“二次回溯”与“非法残留”三种状态。
1、在pred查找循环内部添加条件判断：if (pred->right == nullptr) { /* 第一次访问 */ }；
2、在同一位置添加else if (pred->right == cur) { /* 第二次回溯 */ }；
3、添加else { /* 非法状态：pred->right指向未知地址 */ }；
4、在每次pred->right赋值前后分别打印pred->right与cur地址；
5、在cur = cur->right跳转前打印cur与cur->right值；
6、运行时捕获所有“非法状态”分支并中断执行，防止进一步污染树结构。
五、多线程环境下的Morris遍历隔离策略
Morris遍历通过原地修改树结构实现空间优化，但在多线程并发场景下，多个线程同时对同一棵树执行不同遍历操作将导致right指针竞争，进而引发不可预测的遍历跳变或崩溃；必须通过外部同步机制或数据拷贝保障结构纯净性，不可依赖算法自身线程安全。
1、对共享二叉树对象加读写锁：前序/后序遍历开始前获取独占写锁；
2、遍历执行完毕、且clearMorrisLinks完成后再释放锁；
3、若性能敏感，可采用copy-on-write策略：每次遍历前浅拷贝节点指针，深拷贝value与左右子树引用，确保right指针初始为nullptr；
4、禁止在线程A执行Morris遍历时，线程B对同一棵树做插入、删除或结构调整；
5、日志中记录每次遍历起始时刻与线程ID，用于事后追溯竞争点；
6、单元测试必须覆盖两个线程交替调用前序与后序的情形。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
