C++ 实现二叉树的 Morris 中序遍历逻辑实现及其复杂度数学证明【实战】-C++-PHP中文网

morris中序遍历不用栈也不用递归，因其复用节点空右指针临时构建前驱线索，遍历后恢复原结构，仅需o(1)额外空间（几个指针变量），满足内存受限场景需求。

c++ 实现二叉树的 morris 中序遍历逻辑实现及其复杂度数学证明【实战】

为什么 Morris 中序遍历不用栈也不用递归

Morris 遍历的核心是“临时复用叶子节点的空指针”，把原本指向 null 的 right 指针，临时指向当前节点在中序序列中的前驱（predecessor），从而构建出一条向上的回溯路径。它不依赖系统栈或显式栈，本质是通过修改树结构（遍历后恢复）换取空间 O(1)。

关键前提：二叉树节点必须有 left 和 right 指针，且允许临时修改（遍历结束前会还原）。

如果节点 left 为空，直接访问该节点，然后跳到 right
否则，先找 left 子树的最右节点（即中序前驱）；若其 right 为空，就把它连向当前节点（建立线索），然后转向 left
若其 right 已指向当前节点，说明左子树已处理完——断开线索、访问当前节点、转向 right

代码里最容易漏掉的两个还原操作

很多人写出来能跑通简单样例，但遇到带右子树的深层节点就出错，问题几乎都出在没正确还原被修改的指针。Morris 不是“只读”遍历，它对树有两次侵入：建线索 + 拆线索。

必须确保每次建立的 predecessor->right = curr，在第二次抵达时被设回 nullptr；否则树结构永久损坏，后续遍历或调试会崩。

建线索只发生在 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。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

考虑整棵树的所有 right 指针：原始树有 n−1 条实边（非空指针），其余都是 nullptr。Morris 过程中，每条实边最多被遍历 2 次（向下一次，向上一次），而每条被临时设置的线索（即新增的 right 指向）也只被遍历 1 次（用于回溯），且线索总数 ≤ n（每个节点最多当一次前驱）。