Morris中序遍历不用栈也不用递归，因其复用节点空右指针临时构建前驱线索，遍历后恢复原结构，仅需O(1)额外空间（几个指针变量），满足内存受限场景需求。
为什么 Morris 中序遍历不用栈也不用递归
Morris 遍历的核心是“临时复用叶子节点的空指针”，把原本指向 null 的 right 指针，临时指向当前节点在中序序列中的前驱（predecessor），从而构建出一条向上的回溯路径。它不依赖系统栈或显式栈，本质是通过修改树结构（遍历后恢复）换取空间 O(1)。
关键前提：二叉树节点必须有 left 和 right 指针，且允许临时修改（遍历结束前会还原）。
- 如果节点
left为空，直接访问该节点，然后跳到right - 否则，先找
left子树的最右节点（即中序前驱）；若其right为空，就把它连向当前节点（建立线索），然后转向left - 若其
right已指向当前节点，说明左子树已处理完——断开线索、访问当前节点、转向right
代码里最容易漏掉的两个还原操作
很多人写出来能跑通简单样例，但遇到带右子树的深层节点就出错，问题几乎都出在没正确还原被修改的指针。Morris 不是“只读”遍历，它对树有两次侵入：建线索 + 拆线索。
必须确保每次建立的 predecessor->right = curr，在第二次抵达时被设回 nullptr；否则树结构永久损坏，后续遍历或调试会崩。
立即学习“C++免费学习笔记（深入）”；
- 建线索只发生在
predecessor->right == nullptr时，此时走curr = curr->left - 拆线索必须放在「发现
predecessor->right == curr」的分支里，且紧挨着访问curr之后执行predecessor->right = nullptr - 漏掉这行，同一棵子树可能被重复遍历；更隐蔽的是，若测试用例复用同一棵树多次，第二次调用会直接进入死循环
if (predecessor->right == nullptr) {
predecessor->right = curr;
curr = curr->left;
} else {
predecessor->right = nullptr; // ← 这一行不能少，也不能挪到访问前
result.push_back(curr->val);
curr = curr->right;
}
时间复杂度为什么确实是 O(n)，不是 O(n log n)
直觉上，每个节点可能被访问 2–3 次（找前驱一次、回溯一次、访问一次），容易误以为是 O(nh)。但数学上可严格证明总边访问次数 ≤ 3n。
考虑整棵树的所有 right 指针：原始树有 n−1 条实边（非空指针），其余都是 nullptr。Morris 过程中，每条实边最多被遍历 2 次（向下一次，向上一次），而每条被临时设置的线索（即新增的 right 指向）也只被遍历 1 次（用于回溯），且线索总数 ≤ n（每个节点最多当一次前驱）。
- 所有向下移动（
curr = curr->left或curr = curr->right）总次数 ≤ n - 所有向上回溯（通过前驱的
right跳转）次数 = 线索数 ≤ n - 找前驱过程中的向右游走（在
left子树里一路->right）总次数也 ≤ n —— 因为每条边至多被这种游走经过 1 次
三项加起来 ≤ 3n，故时间复杂度为 O(n)。
和递归/栈版本对比时真正要注意的边界
Morris 的 O(1) 空间代价是有条件的：它要求你能修改原树指针。如果面试题明确说“不能修改树结构”，或者你在生产环境处理共享数据结构，就必须放弃 Morris。
- 线程不安全：多个线程同时 Morris 遍历同一棵树会互相破坏线索
- 迭代器场景不适用：STL 风格的
begin()/next()要求常量时间推进，而 Morris 的单步耗时最坏 O(h)，无法满足 - 调试困难：GDB 或日志打点时看到某节点
right指向了“不该指的地方”，很可能是处于线索未拆除的中间态
真正需要 Morris 的场景其实很窄：嵌入式等极端内存受限环境，或算法题里明确要求 O(1) 额外空间且允许改树。其它时候，老老实实用栈更清晰、更易维护。
