Morris中序遍历的核心思想是利用叶子节点空右指针线索化指向中序后继，遍历后恢复结构，空间复杂度O(1)；关键在于通过前驱节点右指针是否指向当前节点判断左子树是否处理完毕，并在left为空或predecessor->right==current时访问节点，确保最右节点不被遗漏。
Morris中序遍历的核心思想是什么
它不依赖栈或递归，而是利用叶子节点的空右指针临时指向中序后继（即“线索化”），遍历完再恢复树结构。关键在于：每次访问一个节点前，先确保它的左子树已处理完毕；而判断是否“已处理”，就看左子树最右节点的右指针是否已指向当前节点。
- 如果
current->left为空，直接访问current，然后跳到current->right - 否则，找左子树的最右节点（即中序前驱），记为
predecessor - 若
predecessor->right为空，说明左子树未处理，将其指向current，然后进入左子树（current = current->left） - 若
predecessor->right == current，说明左子树已处理过，恢复空指针，访问current，再向右走
这个过程天然避免了额外空间开销，时间复杂度仍是 O(n)，但空间为 O(1)。
为什么标准实现容易漏掉最后一个节点
常见错误写法是只在 current->left == nullptr 时访问节点，却忽略了当整棵树最右节点没有右子树、且其 predecessor->right 被恢复为空后，该节点本身不会被触发访问。
- 标准循环结束条件通常是
current == nullptr，但此时最右路径末端的节点可能还没输出 - 正确做法：只要
current非空，就应保证它最终被访问一次；而访问时机必须在“确认左子树已处理完毕之后” - 优化版把访问逻辑统一放在两个地方：一是
left为空时；二是predecessor->right == current时（此时左子树已遍历完，轮到当前节点）
while (current != nullptr) {
if (current->left == nullptr) {
visit(current); // ← 这里访问
current = current->right;
} else {
auto predecessor = current->left;
while (predecessor->right != nullptr && predecessor->right != current)
predecessor = predecessor->right;
<pre class='brush:php;toolbar:false;'> if (predecessor->right == nullptr) {
predecessor->right = current;
current = current->left;
} else {
predecessor->right = nullptr;
visit(current); // ← 这里也访问
current = current->right;
}
}}
立即学习“C++免费学习笔记（深入）”；
如何安全地复用节点指针而不破坏原树
Morris 的本质是“借用”空右指针做临时链接，所以必须严格成对恢复：
每次设置
predecessor->right = current前，要确认predecessor->right确实为空（即不是已被其他路径设过的线索）每次检测到
predecessor->right == current，必须立刻置为nullptr，否则后续遍历会误判或形成环不要假设树初始状态“干净”：如果函数可能被多次调用，或树被其他算法动过，建议在入口加简单校验（例如检查是否存在指向祖先的右指针），但生产环境更推荐只用于一次性遍历场景
访问函数
visit()应为无副作用纯操作（如仅打印、存入 vector）；若在里面修改current->left/right，会直接破坏线索逻辑使用
auto推导predecessor类型时，确保它是指针类型（TreeNode*），而非引用或值拷贝
和递归/栈版本对比时要注意哪些性能陷阱
Morris 的 O(1) 空间代价，换来的是部分节点被访问两次（每个边最多被走两遍：一次建立线索，一次拆除），所以常数因子比栈版略大；但它真正优势在于确定性——不会因深度过大导致栈溢出。
- 递归版在退化为链表时深度达 O(n)，易爆栈；Morris 完全规避这点
- 栈版需分配 O(h) 内存（h 为高度），而 Morris 对缓存不友好：指针跳跃无局部性，
predecessor查找过程可能引发多次 cache miss - 若你需要在遍历中提前终止（如找第 k 小），Morris 可以随时 break，但要注意：此时树可能处于中间线索状态，若后续还要用，必须手动恢复（一般不建议）
真正容易被忽略的是：Morris 不支持“回溯”或“获取父节点”。一旦离开某个节点，就再也无法返回——这决定了它只适合单向扫描类需求，比如中序建有序数组、验证 BST、求中位数等。
你得接受它是一次性、不可逆、强顺序的遍历方式；想边走边改结构？换别的方法。
