Morris遍历算法（二叉树遍历） 描述 Morris遍历算法是一种可以在O(n)时间内完成二叉树遍历，且仅使用O(1)额外空间的算法。它通过修改树中的临时指针（遍历结束后恢复）来避免使用栈或递归，适用于中序、前序遍历（后序遍历较复杂）。核心思想是利用叶子节点的空指针指向后继节点，从而在遍历时能回溯到上层节点。 解题过程 问题分析 常规二叉树遍历（递归/迭代）需要O(h)的栈空间（h为树高）。 Morris遍历通过 线索二叉树 思想，将空闲指针用于记录回溯路径，实现空间复杂度O(1)。 中序遍历的Morris算法步骤 初始化当前节点 cur 为根节点。 当 cur 不为空时循环： 若 cur 无左子树： 输出 cur 的值（访问当前节点）。 将 cur 指向右子树（ cur = cur.right ）。 若 cur 有左子树： 找到 cur 的前驱节点 pre （即左子树的最右节点）： pre = cur.left 循环向右移动 pre ，直到 pre.right 为空或指向 cur （避免死循环）。 若 pre.right 为空： 将 pre.right 指向 cur （建立临时回溯指针）。 cur 向左移动（ cur = cur.left ）。 若 pre.right 指向 cur （说明已访问过左子树）： 断开临时指针： pre.right = null 。 输出 cur 的值（此时左子树已处理完）。 cur 向右移动（ cur = cur.right ）。 示例演示（中序遍历） 以二叉树 [1,2,3,4,5] 为例（根为2，左子树为1，右子树为4、3、5）： 步骤1： cur=2 ，左子树存在，找到前驱节点 1 （最右节点），将 1.right 指向2。 步骤2： cur=1 ，无左子树，输出1， cur 移至 1.right （即2）。 步骤3： cur=2 ，左子树存在且前驱 1.right 指向2，断开指针，输出2， cur 移至右子树4。 步骤4： cur=4 ，左子树存在，找到前驱节点 3 ，将 3.right 指向4。 步骤5： cur=3 ，无左子树，输出3， cur 移至 3.right （即4）。 步骤6： cur=4 ，左子树存在且前驱 3.right 指向4，断开指针，输出4， cur 移至右子树5。 步骤7： cur=5 ，无左子树，输出5，遍历结束。 输出顺序为 1,2,3,4,5 （正确中序）。 前序遍历的调整 与中序遍历区别：在 第一次访问节点时立即输出 （即建立临时指针前）。 步骤调整： 当 cur 有左子树且前驱 pre.right 为空时，输出 cur 并建立指针。 当 cur 无左子树时，输出 cur 后直接右移。 关键点总结 时间复杂度 ：每个节点被访问两次（一次找前驱，一次遍历），但每个前驱节点最多被找两次，总操作次数为O(n)。 空间复杂度 ：仅使用常数级额外变量（O(1)）。 注意事项 ：遍历过程中临时修改指针，结束后恢复原树结构（已自动断开临时指针）。 通过Morris算法，可在不牺牲时间复杂度的情况下，极大优化空间使用，尤其适用于对空间有严格限制的场景（如嵌入式系统）。