LeetCode二叉树中序遍历：从递归到迭代，吃透树结构的核心逻辑

admin 2026-02-09 阅读:13 评论:0

作为LeetCode第94题，LeetCode二叉树的中序遍历是树结构遍历的“入门级标杆题”——它不仅是大厂技术面试的高频考点（据鳄鱼java算法课2025年统计，90%的互联网大厂面试会涉及树遍历类问题），更是理解树结构“递归特性”与“栈...

作为LeetCode第94题，LeetCode二叉树的中序遍历是树结构遍历的“入门级标杆题”——它不仅是大厂技术面试的高频考点（据鳄鱼java算法课2025年统计，90%的互联网大厂面试会涉及树遍历类问题），更是理解树结构“递归特性”与“栈迭代应用”的核心载体。很多新手第一次接触树遍历会觉得抽象，但通过这道题能快速掌握中序遍历“左-根-右”的核心规则，从递归的简洁实现到迭代的模拟过程，再到O(1)空间的Morris优化，逐步建立对树结构的深度理解。鳄鱼java学员数据显示，吃透这道题后，树遍历类问题的平均通过率从35%提升到95%，足见其核心价值。

题解前置：中序遍历的定义与核心边界用例

要掌握LeetCode二叉树的中序遍历，首先得明确核心规则：中序遍历是按照“左子树→根节点→右子树”的顺序访问二叉树的所有节点，且每个子树的遍历仍遵循这个规则。例如输入二叉树[1,null,2,3]（根节点1，右子节点2，2的左子节点3），中序遍历结果为[1,3,2]。

解题前必须覆盖的边界用例是避免提交错误的关键，鳄鱼java技术导师会反复强调： 1. 空树：输入null，输出空列表； 2. 单节点树：输入[5]，输出[5]； 3. 只有左子树：输入[3,2,null,1]，输出[1,2,3]； 4. 只有右子树：输入[1,null,2,null,3]，输出[1,2,3]； 5. 完全二叉树：输入[4,2,6,1,3,5,7]，输出[1,2,3,4,5,6,7]。

据鳄鱼java学员提交数据，25%的新手会忽略空树的情况，导致代码因空指针报错；15%的新手会搞反遍历顺序，把“左-根-右”写成“根-左-右”，最终提交失败。

递归解法：一行代码搞定，但要理解递归栈的本质

递归是实现中序遍历最简洁的方式，代码仅需几行，核心是利用“树的结构本身具有递归性”的特性：每个节点的左子树和右子树都是一棵二叉树，因此可以递归调用自身遍历左子树，访问根节点，再递归遍历右子树。

Java递归实现代码：

 
import java.util.ArrayList; 
import java.util.List; 
public class Solution {
public List inorderTraversal(TreeNode root) {
List res = new ArrayList<>();
inorder(root, res);
return res;
}
private void inorder(TreeNode node, List<Integer> res) { 
    // 递归终止条件：节点为空，直接返回 
    if (node == null) return; 
    // 遍历左子树 
    inorder(node.left, res); 
    // 访问根节点 
    res.add(node.val); 
    // 遍历右子树 
    inorder(node.right, res); 
} 

}

递归解法的时间复杂度是O(n)，每个节点被访问一次；空间复杂度是O(n)，最坏情况（链状树）下递归栈的深度等于树的节点数。鳄鱼java学员中，很多新手会疑惑“递归栈是什么”，其实递归调用时，Java虚拟机会为每个递归函数调用创建栈帧，存储局部变量和调用状态，这和后面要讲的迭代解法中手动用栈模拟的逻辑完全一致。

需要注意的是，当树的深度超过1000（比如链状树有10000个节点），递归会抛出StackOverflowError，这也是迭代解法需要掌握的原因。

迭代解法：用栈模拟递归，彻底掌握栈的应用

递归的本质是依赖虚拟机的栈，我们可以手动用栈模拟这个过程，实现迭代版的中序遍历，这也是大厂面试更看重的解法——它能体现你对栈的理解，而非仅仅依赖递归的简洁性。

迭代解法的核心步骤（鳄鱼java导师总结的“左入栈-根弹出-右处理”三步法）： 1. 初始化一个空栈，当前节点指向根节点； 2. 循环遍历：将当前节点的所有左子节点依次入栈，直到左子节点为空； 3. 弹出栈顶节点，将其值加入结果列表； 4. 将当前节点指向弹出节点的右子节点，重复步骤2-4。

Java迭代实现代码：

 
import java.util.ArrayList; 
import java.util.List; 
import java.util.Stack; 
public class Solution {
public List inorderTraversal(TreeNode root) {
List res = new ArrayList<>();
Stack stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
// 左子节点全部入栈
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
// 弹出根节点，访问值
curr = stack.pop();
res.add(curr.val);
// 处理右子节点
curr = curr.right;
}
return res;
}
}

迭代解法的时间复杂度仍是O(n)，空间复杂度O(n)（最坏情况栈存储所有左子节点）。鳄鱼java学员常犯的错误是：忘记处理右子节点，或者在左子节点入栈时漏掉curr = curr.left，导致死循环。

Morris遍历：O(1)空间复杂度的进阶优化

如果想进一步优化空间复杂度，达到O(1)的极致，就需要用到Morris遍历（线索二叉树遍历）。它的核心思想是利用树的空闲右指针，将右子节点指向后续要访问的节点，避免使用栈存储节点。

Morris中序遍历的核心步骤： 1. 初始化当前节点curr为根节点； 2. 当curr不为空时： a. 如果curr的左子节点为空，访问curr，curr指向其右子节点； b. 如果curr的左子节点不为空，找到左子树的最右节点（前驱节点）； i. 如果前驱节点的右子节点为空，将其右指针指向curr，curr指向左子节点； ii. 如果前驱节点的右子节点指向curr，说明左子树已遍历完成，访问curr，将前驱节点的右指针置空，curr指向右子节点； 3. 重复步骤2，直到curr为空。

鳄鱼java算法课会强调：Morris遍历虽然空间复杂度更优，但代码实现更复杂，适合面试中体现自己的算法深度，当面试官问“有没有更优的解法”时，能从容回答Morris遍历。

鳄鱼java学员实战：避坑指南与面试技巧

根据鳄鱼java学员的实战经验，做LeetCode二叉树的中序遍历时，需要避开三个常见坑： 1. 递归忘记终止条件：很多新手会漏掉if (node == null) return，导致空指针异常； 2. 迭代循环条件错误：只判断!stack.isEmpty()，漏掉curr != null，导致根节点为空时无法处理； 3. Morris遍历中误判前驱节点：找不到左子树的最右节点，或者忘记重置右指针，导致树结构被修改。

面试中讲解这道题的技巧：先讲递归解法，说明其简洁性和核心逻辑；再讲迭代解法，说明是模拟递归栈的过程，解决递归栈溢出问题；最后提Morris遍历，体现对空间优化的思考——这样的回答能展示你对问题的多层次理解，让面试官眼前一亮。