二叉树三种遍历——Morris遍历O(1)空间的神奇实现

适读人群：Java 后端工程师、准备面试的同学 | 阅读时长：约25分钟 | 难度：Medium（Morris部分Hard）

---

开篇故事

二叉树遍历是我带过的新人里翻车率最高的知识点之一，没有之一。

翻车不是因为不会写递归——递归大家基本都会，套路也熟。翻车是在"用迭代实现三种遍历"这道坎上。前序迭代基本都能写出来，中序迭代需要多想一会，后序迭代……很多人当场卡住。

而 Morris 遍历，很多人连听都没听说过。我第一次接触是在读《算法第四版》，看到"O(1) 空间完成树的遍历"时，我以为自己看错了——树的遍历不是必然要 O(n) 的栈或递归栈吗？后来研究了好几天，才彻底搞懂 Morris 遍历的精妙之处：它利用叶节点的空余 next 指针作为"临时线索"，在不开辟额外空间的情况下，完成了原本需要栈才能做到的回溯。

这篇文章把三种遍历（前序、中序、后序）的三种写法（递归、迭代、Morris）全部实现，每种写法都有完整代码和思路讲解。

---

一、题目解析

题目：LeetCode 94. 二叉树的中序遍历题目：LeetCode 144. 二叉树的前序遍历题目：LeetCode 145. 二叉树的后序遍历

三道题的结构完全一样，只是遍历顺序不同：

• 前序：根 -> 左 -> 右
• 中序：左 -> 根 -> 右
• 后序：左 -> 右 -> 根

示例（以中序为例）：

输入：[1,null,2,3]
输出：[1,3,2]

考点梳理：

1. 递归实现（基础）
2. 迭代实现——用栈模拟递归
3. Morris 遍历——O(1) 空间，利用空指针建立线索

---

二、解法一：递归实现

思路

递归是最自然的实现方式，三种遍历只有操作节点的时机不同。

完整代码

// 前序遍历（144）
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorder(root, result);
        return result;
    }
    
    private void preorder(TreeNode node, List<Integer> result) {
        if (node == null) return;
        result.add(node.val);        // 根
        preorder(node.left, result); // 左
        preorder(node.right, result);// 右
    }
}

// 中序遍历（94）
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }
    
    private void inorder(TreeNode node, List<Integer> result) {
        if (node == null) return;
        inorder(node.left, result);  // 左
        result.add(node.val);        // 根
        inorder(node.right, result); // 右
    }
}

// 后序遍历（145）
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorder(root, result);
        return result;
    }
    
    private void postorder(TreeNode node, List<Integer> result) {
        if (node == null) return;
        postorder(node.left, result);  // 左
        postorder(node.right, result); // 右
        result.add(node.val);          // 根
    }
}

复杂度分析

三种遍历相同：

• 时间复杂度：O(n)。每个节点被访问一次。
• 空间复杂度：O(n)。递归调用栈，最坏情况（链状树）深度为 n。

---

三、解法二：迭代实现（用栈）

前序迭代

把右子节点先压栈，再压左子节点，保证左子节点先出栈（先访问）。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);           // 访问根
            if (node.right != null) stack.push(node.right);  // 先压右
            if (node.left != null) stack.push(node.left);    // 再压左（后进先出，左先访问）
        }
        
        return result;
    }
}

中序迭代

中序是最难迭代的一种，因为需要先深入到最左叶节点，回溯时访问节点，再转向右子树。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode curr = root;
        
        while (curr != null || !stack.isEmpty()) {
            // 一直往左走，把路径上的节点都压栈
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            // 左子树走完，弹出栈顶节点（最左边的节点或回溯到的父节点）
            curr = stack.pop();
            result.add(curr.val);  // 访问
            // 转向右子树
            curr = curr.right;
        }
        
        return result;
    }
}

后序迭代

后序的迭代有一个技巧：后序 = 左右根，可以用"根右左"的顺序访问（类似前序但左右互换），然后把结果反转。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        if (root == null) return result;
        
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.addFirst(node.val);  // 头插，相当于反转
            if (node.left != null) stack.push(node.left);   // 先压左（后访问）
            if (node.right != null) stack.push(node.right); // 再压右（先访问）
        }
        
        return result;
    }
}

复杂度分析

三种遍历相同：

• 时间复杂度：O(n)。每个节点进出栈一次。
• 空间复杂度：O(n)。栈最大深度为树的高度，最坏 O(n)。

---

四、解法三：最优解法——Morris 遍历

核心思想

Morris 遍历利用了二叉树中大量存在的空 right 指针。对于每个节点 cur：

1. 如果 cur 没有左子树，直接访问/记录 cur，移动到右子树
2. 如果 cur 有左子树，找到左子树中序遍历的最后一个节点（即左子树的最右节点，记为 predecessor）
   • 如果 predecessor.right == null：建立临时线索 predecessor.right = cur，cur 移动到左子树
   • 如果 predecessor.right == cur：恢复 predecessor.right = null，访问/记录 cur，cur 移动到右子树

Morris 中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        TreeNode cur = root;
        
        while (cur != null) {
            if (cur.left == null) {
                // 没有左子树，直接访问当前节点，移动到右子树
                result.add(cur.val);
                cur = cur.right;
            } else {
                // 找左子树的最右节点（中序前驱节点）
                TreeNode predecessor = cur.left;
                while (predecessor.right != null && predecessor.right != cur) {
                    predecessor = predecessor.right;
                }
                
                if (predecessor.right == null) {
                    // 第一次到达：建立线索，移动到左子树
                    predecessor.right = cur;
                    cur = cur.left;
                } else {
                    // 第二次到达：恢复线索，访问当前节点，移动到右子树
                    predecessor.right = null;
                    result.add(cur.val);
                    cur = cur.right;
                }
            }
        }
        
        return result;
    }
}

Morris 前序遍历

前序与中序的区别：访问节点的时机从"第二次到达"改为"第一次到达"。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        TreeNode cur = root;
        
        while (cur != null) {
            if (cur.left == null) {
                result.add(cur.val);  // 没有左子树，访问并移动
                cur = cur.right;
            } else {
                TreeNode predecessor = cur.left;
                while (predecessor.right != null && predecessor.right != cur) {
                    predecessor = predecessor.right;
                }
                
                if (predecessor.right == null) {
                    result.add(cur.val);  // 前序：第一次到达时访问
                    predecessor.right = cur;
                    cur = cur.left;
                } else {
                    predecessor.right = null;
                    // 前序：这里不访问（已经在第一次访问过了）
                    cur = cur.right;
                }
            }
        }
        
        return result;
    }
}

Morris 后序遍历

后序最复杂：需要在第二次到达节点时，逆序打印其左子树的最右路径。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        TreeNode cur = root;
        
        while (cur != null) {
            if (cur.left == null) {
                cur = cur.right;
            } else {
                TreeNode predecessor = cur.left;
                while (predecessor.right != null && predecessor.right != cur) {
                    predecessor = predecessor.right;
                }
                
                if (predecessor.right == null) {
                    predecessor.right = cur;
                    cur = cur.left;
                } else {
                    predecessor.right = null;
                    // 后序：逆序打印 cur.left 到 predecessor 这条路径
                    addReversedPath(cur.left, result);
                    cur = cur.right;
                }
            }
        }
        // 最后逆序打印整棵树最右路径
        addReversedPath(root, result);
        
        return result;
    }
    
    // 逆序收集从 node 开始沿右边走到底的路径
    private void addReversedPath(TreeNode node, List<Integer> result) {
        int start = result.size();
        while (node != null) {
            result.add(node.val);
            node = node.right;
        }
        // 反转新加入的部分
        int end = result.size() - 1;
        while (start < end) {
            int temp = result.get(start);
            result.set(start++, result.get(end));
            result.set(end--, temp);
        }
    }
}

复杂度分析（Morris 遍历）

• 时间复杂度：O(n)。每个节点最多被访问两次（建立线索一次，恢复线索一次）。每条"前驱节点搜索"路径的总长度为 O(n)（各路径不重叠）。
• 空间复杂度：O(1)。没有栈，没有递归，只用了常数个指针变量。

提交结果：时间击败约 99% 用户，空间击败约 99% 用户（Morris 版本）。

---

五、举一反三

同类题目

LeetCode 102. 二叉树层序遍历 BFS 的层次遍历，与 DFS 的三种遍历并列为最基础的树遍历。

LeetCode 105. 从前序与中序遍历序列构造二叉树 需要理解前序和中序遍历序列的位置关系。

LeetCode 98. 验证二叉搜索树 中序遍历的典型应用——BST 的中序是有序的。

三种遍历对比

遍历类型	递归空间	迭代技巧	Morris 技巧
前序	O(h)	栈，先压右再压左	第一次到达时访问
中序	O(h)	栈，一路向左再回溯	第二次到达时访问
后序	O(h)	前序变形+反转	第二次到达时逆序打印路径

---

六、踩坑实录

坑一：中序迭代没有外层 while 条件的双重判断

// 错误：只判断栈不空
while (!stack.isEmpty()) { ... }

// 正确：还要判断 curr != null（初始时栈是空的，但 curr 不空）
while (curr != null || !stack.isEmpty()) { ... }

如果只判断栈不空，初始时栈是空的会立刻退出，返回空结果。

坑二：Morris 遍历找前驱节点时忘记 predecessor.right != cur 的判断

// 错误：可能无限循环
while (predecessor.right != null) {
    predecessor = predecessor.right;
}

// 正确：同时检查线索是否已建立
while (predecessor.right != null && predecessor.right != cur) {
    predecessor = predecessor.right;
}

建立线索后，前驱节点的 right 指向了 cur，如果没有第二个条件，找前驱的循环会绕回 cur，进入死循环。

坑三：Morris 遍历结束后树结构未恢复

Morris 遍历过程中建立了临时线索（修改了节点的 right 指针），但在恢复阶段（predecessor.right == cur 的分支）会把线索删除。只要遍历完整执行，树结构会完全恢复原样。但如果中途出现异常退出，树结构会被破坏——这是 Morris 遍历在工程代码里需要注意的地方。

坑四：后序迭代的"反转技巧"不理解

后序迭代的关键是：后序遍历（左右根）= 反转（根右左）。用前序遍历的变体（先访问根，再右子树，再左子树）得到"根右左"序列，然后反转就得到后序序列。这个思路很巧妙，但初次接触容易觉得奇怪。

坑五：递归深度在极端情况下栈溢出

当树退化为链状（每个节点只有右子节点）时，递归深度等于节点数，可能导致 Java StackOverflowError。LeetCode 题目的测试用例一般不会触发这个问题，但在生产代码中处理大规模树时，要考虑用迭代替换递归。

---

七、总结

三种遍历、三种实现方式，最终形成了一个 3x3 的知识矩阵：

递归版本是入门，面试里要求快速实现，不能有任何卡顿；迭代版本是进阶，体现了对栈和程序计数器的本质理解；Morris 遍历是高手，O(1) 空间的实现展示了对指针和树结构的深刻理解。

实际面试中，能把迭代版本流利写出来就算过关；如果能主动提出 Morris 遍历并讲清楚思路，基本是加分项。Morris 后序遍历是三种里最难的，如果时间允许，值得专门研究一下"为什么要逆序打印右路径"的原理。

---

Morris 遍历你之前了解吗？评论区聊聊，点个在看支持。