Morris中序遍历不用栈也不用递归，因其核心是临时复用节点空right指针建立指向中序后继的线索，遍历后立即恢复原结构，以O(1)额外空间实现线性时间遍历，但要求树可修改且无并发访问。
为什么 Morris 中序遍历不用栈也不用递归
因为它的核心是临时篡改树的空 right 指针，把二叉树“链表化”成一条向右延伸的路径，遍历完再恢复原结构。它本质上是用线索（thread）代替显式栈空间，所以空间复杂度能压到 O(1)（不计输出空间）。但注意：它会短暂修改原树指针，如果树被多线程访问或不允许修改，就不能直接用。
Morris 遍历中判断前驱节点的关键逻辑
对当前节点 curr，它的中序前驱是左子树的最右节点。这个判断必须严格满足两个条件：
-
curr->left != nullptr—— 否则没有前驱，直接向右走 - 从
curr->left出发一路right，直到right == nullptr或right == curr
如果最终停在 right == nullptr，说明还没建立线索，要让它指向 curr，然后 curr = curr->left；如果停在 right == curr，说明已访问过左子树，此时输出 curr->val，并恢复 predecessor->right = nullptr，再向右走。
实际写代码时最容易漏掉的三处恢复操作
Morris 的“可逆性”全靠这三步，漏任何一步都会导致树结构损坏或死循环：
立即学习“C++免费学习笔记（深入）”；
- 建立线索前，必须确保
predecessor->right是nullptr，不能直接赋值 - 当发现
predecessor->right == curr时，必须立刻设为nullptr，否则下次再进这个分支会误判 - 输出节点值的位置只能在“已回溯到该节点且左子树处理完毕”的时刻，也就是第二次抵达该节点时——即
predecessor->right == curr分支里
常见错误是把 cout val 放在第一次抵达（建线索）分支里，结果重复输出或顺序错乱。
时间复杂度为什么是 O(n) 而不是 O(n log n)
表面上看，每个节点可能被访问多次（比如找前驱要向下走），但关键在于：整棵树的所有边最多被遍历 **两次** —— 一次是建立线索（向右走），一次是恢复线索（再向右走）。所有“向下找前驱”的路径加起来，不超过 2n 条边。所以均摊下来，每个节点只被常数次访问。实测在满二叉树上，curr 移动总次数约 2.5n，远低于 n log n。
真正要注意的是：Morris 不适合做带副作用的遍历（比如边遍历边删节点），因为指针临时重定向会让逻辑失控；另外，它无法自然支持中序的“前驱/后继查询”，仅适用于一次性完整遍历。
