morris中序遍历可在o(1)空间复杂度下完成：通过临时修改右指针建立线索，遍历后恢复原状；每条边最多访问3次，时间复杂度o(n)；仅用cur、prev等常数个指针变量，无递归栈或辅助栈。

要在不使用递归栈和显式辅助栈的前提下完成二叉树中序遍历，且确保空间复杂度严格为 O(1)，必须借助Morris遍历的线索化思想——它通过临时修改树结构建立前驱后继链接，遍历完成后立即恢复原状。

Morris中序遍历的完整实现

定义节点结构并编写主遍历函数：

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };

vector morrisInorder(TreeNode* root) { vector res; TreeNode* cur = root; while (cur) { if (!cur->left) { res.push_back(cur->val); cur = cur->right; } else { TreeNode* prev = cur->left; while (prev->right && prev->right != cur) prev = prev->right; if (!prev->right) { prev->right = cur; cur = cur->left; } else { prev->right = nullptr; res.push_back(cur->val); cur = cur->right; } } } return res; }

关键步骤的数学建模与路径分析

Morris遍历中每条边最多被访问3次：第一次建立线索时走一次，第二次沿线索回溯时走一次，第三次恢复指针时走一次。设树有 n 个节点，则边数为 n−1，总访问次数 ≤ 3(n−1)。因此时间复杂度为 O(n)，且每次访问只使用常数额外变量（cur、prev、res仅存结果不计入工作空间）。

C++14

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

下载

【必须保证每个节点的右指针在恢复前只被修改一次】，否则会导致链路错乱或无限循环。判断条件 prev->right == cur 是识别已建立线索的唯一依据，不可省略。

空间复杂度的严格证明

第一步：定义工作空间 S 为算法执行过程中除输入树和输出容器外，所有显式分配的变量所占空间。此处仅有 cur、prev 两个指针变量及若干临时比较变量。

第二步：观察指针变量生命周期。cur 始终指向当前处理节点，prev 在内层 while 中复用；二者地址不随树规模增长而增加，始终为固定大小（通常 8 字节/指针）。

第三步：排除隐式栈空间。递归调用栈深度可能达 O(n)，但本算法全程无函数调用，无 call 指令压栈行为，CPU 栈帧深度恒为 1。

第四步：形式化结论。对任意 n ∈ ℕ⁺，S(n) = C，其中 C 为与 n 无关的常数，故 S(n) ∈ O(1)。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！