morris前序遍历核心是临时借用左子树最右节点的空右指针建立回溯线索，首次抵达节点时立即访问以保证“根→左→右”顺序，遍历后恢复指针，实现o(1)空间复杂度。
Morris 前序遍历的核心思想是“临时借用右指针建链，遍历完恢复原结构”
它不依赖栈或递归调用栈，真正实现 O(1) 额外空间（仅用几个指针变量）。关键在于：对每个有左子树的节点 cur，找到其左子树的最右节点 predecessor，把它的 right 指针临时指向 cur，形成向上的“线索”，从而在回溯时无需栈就能返回父节点。
注意：这不是“破坏原树”，而是**可逆的临时改造**——每次利用完 predecessor->right 后，都会把它重置为 nullptr。
前序遍历中“访问时机”必须在第一次抵达节点时，且要区分线索边和原始边
和中序不同，前序要求“根 → 左 → 右”，所以访问动作必须放在进入节点的第一时间，但此时还不能确定该节点是否已被线索连过。因此实际逻辑分两种情况：
- 若
cur->left == nullptr：直接访问cur，然后跳到cur->right - 若
cur->left != nullptr：先找predecessor（左子树最右节点）
→ 若predecessor->right == nullptr：说明是首次到达cur，此时访问cur，再建立线索：predecessor->right = cur，然后进入左子树（cur = cur->left）
→ 若predecessor->right == cur：说明已从左子树绕回，线索是“回边”，此时断开线索（predecessor->right = nullptr），并转向右子树（cur = cur->right）
漏掉“首次就访问”这一步，就会变成中序；混淆 predecessor->right 的两种状态，会导致死循环或漏节点。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
典型错误：忘记重置线索、误判 predecessor、空指针解引用
常见崩溃或无限循环都源于这三处：
-
predecessor查找必须严格：从cur->left出发，持续走right直到right == nullptr或right == cur；若写成while (pre->right)且未判断pre->right == cur，会陷入环 - 建立线索前没判空：
if (predecessor->right == nullptr)必须在访问predecessor->right之前做，否则当predecessor为nullptr（比如cur->left为空）时直接崩 - 断开线索后没更新
cur：若在predecessor->right == cur分支里只恢复指针却不执行cur = cur->right，就会卡在当前节点反复检测同一条线索
一个最小可复现错误示例：if (pre->right) pre = pre->right; —— 这行既没处理 pre->right == cur 的终止条件，又没防 pre 为空，大概率段错误。
空间复杂度确实是严格的 O(1)，但隐含常数项不可忽略
数学上，额外空间只用于存储 cur、predecessor、tmp 等固定个数的指针变量，与树节点数 n 无关，故空间复杂度为 O(1)。但这不意味着“不占内存”——它仍需约 3~4 个指针（64 位系统下就是 24~32 字节），且所有操作都在原树的 right 字段上原地腾挪。
真正容易被忽略的是：Morris 遍历**时间复杂度是 O(n)，但常数因子比递归大**。因为每个节点最多被访问 2 次（一次找 predecessor，一次沿线索返回），而递归/栈方式平均只访问 1 次。线上高频调用时，这个两倍开销可能成为瓶颈。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
