二叉树的中序遍历（非递归与Morris遍历）

字数 2695 2025-12-15 12:07:52

二叉树的中序遍历（非递归与Morris遍历）

二叉树的中序遍历顺序是“左子树 -> 根节点 -> 右子树”。对于一个节点，先访问其左子树，再访问自身，最后访问右子树。我将详细讲解其非递归实现和Morris遍历算法，并对比它们的思路、步骤、时间与空间复杂度。

1. 题目描述

给定一个二叉树的根节点 root，返回它的中序遍历结果。要求分别用非递归（使用栈）和Morris遍历（无需栈，空间O(1)）两种方法实现。

2. 非递归（迭代）解法

思路是模拟递归过程，通过栈来显式维护待处理的节点。

详细步骤

初始化一个空栈 stack，并将当前节点 curr 指向根节点。
进入一个循环，条件是 curr 不为空或栈不为空。
在循环内部：
- 如果 curr 不为空，说明当前节点有左子树需要优先处理。我们将 curr 入栈，然后将 curr 移动到其左子节点（curr = curr.left）。这相当于“深入”左子树。
- 如果 curr 为空，说明已经到达某个节点的最左端（即左子树已处理完毕，或没有左子树）。此时我们从栈顶弹出一个节点，这个节点就是下一个应该访问的节点。我们访问它（例如，将值加入结果列表），然后将 curr 指向这个弹出节点的右子节点（curr = node.right），准备开始处理其右子树。

示例与代码逻辑

假设一棵简单的树：

    1
   / \
  2   3

步骤模拟：

初始：stack=[], curr=1。
curr=1 不为空，入栈，stack=[1]。curr 指向1的左子节点2。
curr=2 不为空，入栈，stack=[1,2]。curr 指向2的左子节点（空）。
curr 为空，从栈顶弹出节点2，访问节点2。stack=[1]。curr 指向节点2的右子节点（空）。
curr 为空，栈非空，从栈顶弹出节点1，访问节点1。stack=[]。curr 指向节点1的右子节点3。
curr=3 不为空，入栈，stack=[3]。curr 指向3的左子节点（空）。
curr 为空，从栈顶弹出节点3，访问节点3。stack=[]。curr 指向节点3的右子节点（空）。
curr 为空且栈空，循环结束。中序遍历结果为 [2, 1, 3]。

时间复杂度：每个节点恰好入栈一次，出栈一次，访问一次。因此时间复杂度为 O(n)，其中 n 是节点数。
空间复杂度：栈的最大深度等于树的高度，最坏情况下（树退化成链表）为 O(n)。

3. Morris 中序遍历

Morris遍历是一种巧妙的算法，它能在不使用栈或递归的情况下实现中序遍历，核心思想是利用树中空闲的指针（节点的右子节点指针）来建立临时链接，从而在不增加额外空间的情况下记录回溯路径。

算法核心思想

对于当前节点 curr：

如果 curr 没有左子树，则可以直接访问 curr，然后转向其右子树。
如果 curr 有左子树，我们需要找到 curr 在中序遍历下的前驱节点（即 curr 左子树中最右边的节点）。
- 检查前驱节点的右指针：
  - 如果前驱节点的右指针为空，说明这是第一次访问 curr 的左子树。我们将前驱节点的右指针指向 curr（建立临时链接），然后 curr 移动到其左子节点继续处理。
  - 如果前驱节点的右指针已经指向 curr，说明我们已经处理完了 curr 的左子树，且刚刚通过这个临时链接回溯了回来。此时，我们应该访问 curr 节点，然后断开这个临时链接（将前驱节点的右指针恢复为空），并将 curr 移动到其右子节点。

详细步骤

初始化 curr 为根节点。
当 curr 不为空时，进行循环：
a. 如果 curr 的左子节点为空：
- 访问 curr。
- 将 curr 更新为其右子节点。
  b. 否则（curr 的左子节点不为空）：
- 在 curr 的左子树中，找到 curr 的中序前驱节点 pre。具体做法是：从 curr 的左子节点开始，一直向右走，直到某个节点的右子节点为空或指向 curr 本身。
- 检查前驱节点 pre 的右指针：
  - 如果 pre.right 为空：建立临时链接，pre.right = curr。然后将 curr 更新为其左子节点。
  - 如果 pre.right == curr：说明左子树已处理完毕。断开临时链接，pre.right = null。访问 curr。然后将 curr 更新为其右子节点。

示例与代码逻辑

同样以树 [1,2,3] 为例：

初始：curr=1，它有左子树。
找到 curr=1 的前驱节点：在左子树（节点2）中一直向右，发现节点2的右子节点为空，所以 pre=2，且 pre.right=null。
建立临时链接：pre.right=curr，即 2.right=1。curr 移动到其左子节点2。
现在 curr=2，它没有左子树，所以直接访问节点2。curr 移动到其右子节点（此时是1，因为临时链接）。
现在 curr=1，它有左子树。找到其前驱节点：在左子树（节点2）中一直向右，发现节点2的右子节点指向 curr 自身（即1）。
断开临时链接：pre.right=null。访问节点1。curr 移动到其右子节点3。
现在 curr=3，它没有左子树，直接访问节点3。curr 移动到其右子节点（空）。
curr 为空，结束。遍历结果为 [2, 1, 3]。

时间复杂度：虽然看似有两个嵌套循环（寻找前驱节点），但每个节点被访问的次数是常数次，每个前驱节点的寻找过程会随着临时链接的建立和断开，使得每条边最多被经过两次。因此总时间复杂度仍为 O(n)。
空间复杂度：只使用了固定的几个指针变量，因此是 O(1)。

4. 对比总结

非递归（迭代）：逻辑直观，需要显式栈，空间复杂度为 O(h)，其中 h 是树高。是面试中最常被要求写的版本。
Morris遍历：算法精巧，实现了 O(1) 额外空间的遍历，但会修改树的结构（临时链接），并在遍历过程中恢复。通常作为进阶考点，用于考察对树遍历和指针操作的理解深度。

理解这两种方法，不仅有助于解答二叉树遍历相关问题，还能加深对树的结构操作和空间复杂度优化的认识。

二叉树的中序遍历（非递归与Morris遍历）二叉树的中序遍历顺序是“左子树 -> 根节点 -> 右子树”。对于一个节点，先访问其左子树，再访问自身，最后访问右子树。我将详细讲解其非递归实现和Morris遍历算法，并对比它们的思路、步骤、时间与空间复杂度。 1. 题目描述给定一个二叉树的根节点 root ，返回它的中序遍历结果。要求分别用非递归（使用栈）和Morris遍历（无需栈，空间O(1)）两种方法实现。 2. 非递归（迭代）解法思路是模拟递归过程，通过栈来显式维护待处理的节点。详细步骤初始化一个空栈 stack ，并将当前节点 curr 指向根节点。进入一个循环，条件是 curr 不为空或栈不为空。在循环内部：如果 curr 不为空，说明当前节点有左子树需要优先处理。我们将 curr 入栈，然后将 curr 移动到其左子节点（ curr = curr.left ）。这相当于“深入”左子树。如果 curr 为空，说明已经到达某个节点的最左端（即左子树已处理完毕，或没有左子树）。此时我们从栈顶弹出一个节点，这个节点就是下一个应该访问的节点。我们访问它（例如，将值加入结果列表），然后将 curr 指向这个弹出节点的右子节点（ curr = node.right ），准备开始处理其右子树。示例与代码逻辑假设一棵简单的树：步骤模拟：初始： stack=[] , curr=1 。 curr=1 不为空，入栈， stack=[1] 。 curr 指向1的左子节点2。 curr=2 不为空，入栈， stack=[1,2] 。 curr 指向2的左子节点（空）。 curr 为空，从栈顶弹出节点2，访问节点2。 stack=[1] 。 curr 指向节点2的右子节点（空）。 curr 为空，栈非空，从栈顶弹出节点1，访问节点1。 stack=[] 。 curr 指向节点1的右子节点3。 curr=3 不为空，入栈， stack=[3] 。 curr 指向3的左子节点（空）。 curr 为空，从栈顶弹出节点3，访问节点3。 stack=[] 。 curr 指向节点3的右子节点（空）。 curr 为空且栈空，循环结束。中序遍历结果为 [2, 1, 3] 。时间复杂度：每个节点恰好入栈一次，出栈一次，访问一次。因此时间复杂度为 O(n)，其中 n 是节点数。空间复杂度：栈的最大深度等于树的高度，最坏情况下（树退化成链表）为 O(n)。 3. Morris 中序遍历 Morris遍历是一种巧妙的算法，它能在不使用栈或递归的情况下实现中序遍历，核心思想是利用树中空闲的指针（节点的右子节点指针）来建立临时链接，从而在不增加额外空间的情况下记录回溯路径。算法核心思想对于当前节点 curr ：如果 curr 没有左子树，则可以直接访问 curr ，然后转向其右子树。如果 curr 有左子树，我们需要找到 curr 在中序遍历下的前驱节点（即 curr 左子树中最右边的节点）。检查前驱节点的右指针：如果前驱节点的右指针为空，说明这是第一次访问 curr 的左子树。我们将前驱节点的右指针指向 curr （建立临时链接），然后 curr 移动到其左子节点继续处理。如果前驱节点的右指针已经指向 curr ，说明我们已经处理完了 curr 的左子树，且刚刚通过这个临时链接回溯了回来。此时，我们应该访问 curr 节点，然后断开这个临时链接（将前驱节点的右指针恢复为空），并将 curr 移动到其右子节点。详细步骤初始化 curr 为根节点。当 curr 不为空时，进行循环： a. 如果 curr 的左子节点为空：访问 curr 。将 curr 更新为其右子节点。 b. 否则（ curr 的左子节点不为空）：在 curr 的左子树中，找到 curr 的中序前驱节点 pre 。具体做法是：从 curr 的左子节点开始，一直向右走，直到某个节点的右子节点为空或指向 curr 本身。检查前驱节点 pre 的右指针：如果 pre.right 为空：建立临时链接， pre.right = curr 。然后将 curr 更新为其左子节点。如果 pre.right == curr ：说明左子树已处理完毕。断开临时链接， pre.right = null 。访问 curr 。然后将 curr 更新为其右子节点。示例与代码逻辑同样以树 [1,2,3] 为例：初始： curr=1 ，它有左子树。找到 curr=1 的前驱节点：在左子树（节点2）中一直向右，发现节点2的右子节点为空，所以 pre=2 ，且 pre.right=null 。建立临时链接： pre.right=curr ，即 2.right=1 。 curr 移动到其左子节点2。现在 curr=2 ，它没有左子树，所以直接访问节点2。 curr 移动到其右子节点（此时是1，因为临时链接）。现在 curr=1 ，它有左子树。找到其前驱节点：在左子树（节点2）中一直向右，发现节点2的右子节点指向 curr 自身（即1）。断开临时链接： pre.right=null 。访问节点1。 curr 移动到其右子节点3。现在 curr=3 ，它没有左子树，直接访问节点3。 curr 移动到其右子节点（空）。 curr 为空，结束。遍历结果为 [2, 1, 3] 。时间复杂度：虽然看似有两个嵌套循环（寻找前驱节点），但每个节点被访问的次数是常数次，每个前驱节点的寻找过程会随着临时链接的建立和断开，使得每条边最多被经过两次。因此总时间复杂度仍为 O(n)。空间复杂度：只使用了固定的几个指针变量，因此是 O(1)。 4. 对比总结非递归（迭代）：逻辑直观，需要显式栈，空间复杂度为 O(h)，其中 h 是树高。是面试中最常被要求写的版本。 Morris遍历：算法精巧，实现了 O(1) 额外空间的遍历，但会修改树的结构（临时链接），并在遍历过程中恢复。通常作为进阶考点，用于考察对树遍历和指针操作的理解深度。理解这两种方法，不仅有助于解答二叉树遍历相关问题，还能加深对树的结构操作和空间复杂度优化的认识。