Morris中序遍历的核心思想是利用节点空闲的右指针临时建立指向中序后继的线索，遍历后恢复原结构，实现O(1)空间复杂度；其关键操作包括：若当前节点无左子树则直接访问并右移，否则找左子树最右节点作为前驱，若其右指针为空则建立线索并左移，若已指向当前节点则访问当前节点、拆除线索并右移。
Morris 中序遍历的核心思想是啥
它用二叉树节点原本空闲的 right 指针（对左子树为空的节点）临时“借用”为线索，指向中序后继，从而避免递归栈或显式栈，把空间复杂度压到 O(1)。不是靠额外容器，而是靠动态改指针、再恢复——本质是用时间换空间，且不破坏原树结构（遍历完所有指针都复原）。
关键判断点：当前节点 cur 有无左子树。没有就直接访问并走向 cur->right；有，就找它的中序前驱（左子树最右节点），并利用其 right 指针做标记。
怎么写一个不出错的 Morris 中序循环体
错误常出在前驱查找、线索建立/拆除、以及访问时机三处。下面列出必须严格遵守的操作逻辑：
- 当
cur->left == nullptr：直接visit(cur)，然后cur = cur->right - 当
cur->left != nullptr：先找前驱pred（即cur->left的最右节点，且要求pred->right == nullptr或== cur） - 若
pred->right == nullptr：说明第一次到cur，建线索：pred->right = cur，然后cur = cur->left - 若
pred->right == cur：说明左子树已处理完，该访问cur了，先visit(cur)，再拆线索：pred->right = nullptr，最后cur = cur->right
注意：访问操作只发生在两种情形下——cur 无左子树时，或前驱已连回 cur（即第二次抵达）时。漏掉任一，就会跳过节点或重复访问。
为什么空间复杂度真是 O(1)？数学上怎么证
所谓空间复杂度，是指算法运行过程中「额外」使用的内存单元数量，与输入规模 n（节点数）无关。Morris 遍历只用了固定个数的指针变量：cur、pred、可能还有 temp，不管树多大，都是常数个 TreeNode* 变量，即 O(1) 空间。
有人误以为“修改了指针所以用了额外空间”，但这是误解：pred->right 原本就属于节点内部字段，只是临时复用其存储语义，并未 new 新对象、也未申请堆内存。整个过程没调用 malloc、new、std::stack 等任何动态分配操作。
形式化地说：设树含 n 个节点，每个节点已有 left 和 right 成员。算法仅读写这些已有字段，辅助变量总数 ≤ 3，故额外空间 = 3 × sizeof(TreeNode*)，为常数。
实战中最容易被忽略的边界和坑
真实写的时候，这几个点几乎必踩一次：
-
pred查找循环里忘记判pred->right != cur，导致死循环（尤其当树含环或人为构造异常时） - 在
pred->right == cur分支里，先改了pred->right = nullptr，却忘了紧接着visit(cur)—— 结果根节点本身被跳过 - 把
visit()写成递归调用或塞进 lambda 捕获大量上下文，无意中引入隐式栈，破功 - 测试用例用了
std::vector存结果，这不算算法空间，但若在遍历中边走边push_back，要注意别让 vector 的扩容干扰你对“纯遍历空间”的判断
真正考验实现功力的地方，不在主干逻辑，而在如何让每一条指针赋值都有明确的进入条件和退出保障——尤其是 pred->right 的两次赋值（= cur 和 = nullptr）必须严格配对，且只发生一次。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
