morris中序遍历是唯一满足o(1)空间复杂度的确定性算法，通过动态复用空右指针构建并拆除线索：从根开始，若左空则输出并向右；否则找左子树最右节点predecessor，未建线索则建立并左移，已建则恢复、输出、向右移。
要在不使用递归栈和显式辅助栈的前提下完成二叉树中序遍历，并将空间复杂度严格压到 O(1)，必须借助线索化思想动态复用空右指针——Morris 遍历正是唯一满足该约束的确定性算法，其核心在于临时构建与拆除线索的过程控制。
Morris 中序遍历代码实现
第一步：从根节点开始，当前节点记为 cur。
第二步：若 cur 的左子节点为空，直接输出 cur→val，并令 cur = cur→right。
第三步：若 cur 的左子节点非空，则找到其左子树的最右节点（即中序前驱的右子树尽头），记为 predecessor。
第四步：检查 predecessor→right：
→ 若为 nullptr，说明尚未建立线索，令 predecessor→right = cur，cur 向左移动（cur = cur→left）；
→ 若等于 cur，说明已访问过左子树，此时恢复树结构（predecessor→right = nullptr），输出 cur→val，cur 向右移动（cur = cur→right）。
关键边界处理与易错点
方法一：处理只有左链的退化树（如 5→4→3→2→1，全左斜树）
必须确保每次 predecessor 查找都走到「左子树中最右的节点」，而不是简单取 left→right；否则在节点 2 处会误判 predecessor 为 nullptr，导致无限循环。
方法二：处理叶子节点的右指针复原
当某节点无右子树且已被作为 predecessor 使用过，其 right 域曾被设为父节点，【必须在此时置为 nullptr，否则后续遍历会跳转到错误父节点】。
方法三：空树输入
直接返回，不执行任何指针操作，避免对 nullptr 解引用。
空间复杂度 O(1) 的数学证明
设二叉树含 n 个节点。算法仅使用 cur、predecessor 两个指针变量及若干布尔临时量，总空间占用为常数。
关键在于：所有额外指针修改均发生在原树的空右指针上（即满足 node→left == nullptr 的节点，其 node→right 本无效），修改次数有上界。
每条线索（predecessor→right = cur）最多被建立 1 次、拆除 1 次；而每个节点至多成为 1 次 predecessor（因其右指针只被一个祖先借用），也至多被 1 个 predecessor 指向（因每个节点最多有一个中序前驱）；故总线索操作数 ≤ 2n。
因此，额外存储单元数量与 n 无关，空间复杂度严格为 Θ(1)。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
