#94
简单
中频
迭代法二叉树的中序遍历
这是一道围绕树、二叉树、递归展开的高频练习。建议先掌握「迭代法」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
树
二叉树
递归
题目分析
这道题表面上是在处理「二叉树的中序遍历」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考 树、二叉树 这些能力。这类题通常不难想到总体方向，真正容易乱的是遍历顺序、边界收缩和状态更新的先后关系。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：用栈一路向左压入节点，弹栈访问当前节点后，再转去处理它的右子树。
推荐代码
推荐解法：迭代法
时间复杂度： O(n)
空间复杂度： O(n)
核心思路： 用栈一路向左压入节点，弹栈访问当前节点后，再转去处理它的右子树。
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
Deque<TreeNode> stk = new LinkedList<TreeNode>();
while (root != null || !stk.isEmpty()) {
while (root != null) {
stk.push(root);
root = root.left;
}
root = stk.pop();
res.add(root.val);
root = root.right;
}
return res;
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
结构化讲解
面试时怎么讲
开场思路
这题我会用栈模拟递归版中序遍历。
核心过程
- 先一路把当前节点和它的左链压进栈。
- 左边走到底后，弹出栈顶并访问它。
- 访问完当前节点后，把指针切到它的右子树。
- 重复这个过程直到栈空且当前节点为空。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(n)。
面试补一句：中序迭代的模板可以概括成四个字：压左、弹根。
核心思路
中序遍历的顺序是左、根、右。迭代写法的关键，是用栈显式保存“还没访问根节点、但左边已经在路上”的状态。
步骤讲解
1
一路向左压栈
当前节点不为空时，持续压栈并向左走到底。
为什么这样做：中序遍历必须先处理左子树。
对应代码提示：while (node != null) { stack.push(node); node = node.left; }
2
弹栈访问当前节点
左路走到底后，弹出栈顶并记录它的值。
为什么这样做：这时该节点左子树已经全部处理完，可以访问根节点。
对应代码提示：TreeNode node = stack.pop(); answer.add(node.val);
3
转去右子树继续同样过程
访问完当前节点后，把指针切到它的右子树。
为什么这样做：中序顺序的最后一步是处理右子树。
对应代码提示：node = node.right;
易错点
只压一次左子节点
会漏掉更深层左子树，顺序不完整。
正确理解：必须用 while 一路向左压到底。
弹栈后忘记转到右子树
结果只会遍历左链和根节点。
正确理解：每次访问当前节点后都要令
node = node.right。把栈顶当成已访问节点重复处理
控制流写乱后会造成死循环或重复访问。
正确理解：遵循固定模板：压左、弹栈、访问、转右。
复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(n)
比其他方案更好在哪里：比递归法更适合延伸到统一前中后序的栈写法。
适用判断：需要把树递归改写成迭代时，中序遍历的标准模板就是“栈 + 左链”。
额外提醒
- 栈里存的是“左子树还在展开中的祖先节点”。
其他语言 / 其他解法
递归法
递归实现二叉树的中序遍历，按照左-根-右的顺序访问节点。
递归法
递归实现二叉树的中序遍历，按照左-根-右的顺序访问节点。
时间复杂度：O(n)
空间复杂度：O(h)
一句话思路：递归实现二叉树的中序遍历，按照左-根-右的顺序访问节点。
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
inorder(root, res);
return res;
}
public void inorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
inorder(root.left, res);
res.add(root.val);
inorder(root.right, res);
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
动画演示
如果你还没完全看懂，可以展开动画演示。
迭代法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
迭代法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入二叉树结构（用逗号分隔，null表示空节点），然后点击开始
中序遍历结果:
递归法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
递归法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入二叉树结构（用逗号分隔，null表示空节点），然后点击开始
中序遍历结果:
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。