二叉树必刷 2 题｜中序遍历（统一迭代防溢出）+ 最大深度（极简递归）

目录

一、力扣94. 二叉树的中序遍历（统一迭代法，告别递归栈溢出）

解题思路

优化后代码（注释清晰，可直接复制提交）

二、力扣104. 二叉树的最大深度（后序遍历，极简递归解法）

解题思路

优化后代码（极简高效，注释易懂）

总结

一、力扣94. 二叉树的中序遍历（统一迭代法，告别递归栈溢出）

先唠中序遍历！核心逻辑就是「左 → 中 → 右」，递归写法确实简单到离谱，但遇到深层二叉树分分钟栈溢出😭 今天给大家安利一种统一迭代法，用栈+null标志位，不用区分左右节点的处理逻辑，通用性拉满，记一次就能套用所有二叉树遍历场景，谁用谁夸！

解题思路

敲黑板！思路超简单，一步步来：

1. 用栈存节点，根节点不为空就先入栈，启动遍历；

2. 循环掏栈顶节点，分两种情况判断：

- 节点不为null：说明还没处理，先弹出，按「右 → 中 → null → 左」的顺序再入栈（null就是“该处理这个节点了”的信号）；

- 节点为null：直接弹出null，再掏出下一个节点，加入结果集就完事；

3. 栈空了就结束，完美实现「左→中→右」，一点不绕！

2. 循环遍历栈，每次取栈顶节点判断：

- 若节点不为null：说明未处理，先弹出节点，按「右 → 中 → null → 左」的顺序入栈（null作为处理标志）；

- 若节点为null：说明栈顶下一个节点是待处理的「中节点」，弹出null后，取出中节点并加入结果集；

3. 循环结束，返回结果集，完美实现「左→中→右」的中序遍历。

优化后代码（注释清晰，可直接复制提交）

/** * Definition for a binary tree node. * public 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; * } * } */ class Solution { public List<Integer> inorderTraversal(TreeNode root) { // 统一迭代法核心：用null标志位区分「未处理节点」和「待取值节点」 List<Integer> result = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); // 根节点不为空时，先入栈启动遍历 if (root != null) { stack.push(root); } // 栈不为空则持续遍历 while (!stack.isEmpty()) { TreeNode node = stack.peek(); if (node != null) { // 1. 弹出当前节点，按「右→中→null→左」入栈，保证左节点优先处理 stack.pop(); // 右节点先入栈（后续会被后处理） if (node.right != null) { stack.push(node.right); } // 中间节点入栈，后面紧跟null标志位，标记为「待处理」 stack.push(node); stack.push(null); // 左节点最后入栈（优先被处理） if (node.left != null) { stack.push(node.left); } } else { // 2. 遇到null标志位，弹出null，取出待处理的中间节点，加入结果集 stack.pop(); node = stack.pop(); result.add(node.val); } } return result; } }

✨ 亮点暴击！统一迭代法不用单独处理左右子树，代码模板化拉满，后续做前序、后序遍历，只需要调整入栈顺序，记一次就能复用～ 彻底解决递归栈溢出的坑，效率直接拉满，新手也能轻松上手！

二、力扣104. 二叉树的最大深度（后序遍历，极简递归解法）

再来看最大深度！说白了就是求「从根节点到最远叶子节点的最长路径有多少个节点」。这道题真的是新手福利，用后序遍历思路写，几行代码就能搞定，逻辑简单到不用动脑子，面试写这个写法，简洁又加分！

解题思路

思路拆解，小白也能看懂：

1. 递归终止条件：节点为null，说明这个分支没深度，返回0；

2. 后序遍历三步走：先递归算左子树深度，再算右子树深度；

3. 当前节点的深度 = 左右子树深度的最大值 + 1（加1是因为要算上当前节点本身哦）；

4. 递归回溯，最后返回根节点的深度，就是二叉树的最大深度啦！

2. 后序遍历逻辑：先递归计算左子树的深度，再递归计算右子树的深度；

3. 当前节点的深度 = 左、右子树深度的最大值 + 1（加1是因为要包含当前节点本身）；

4. 递归回溯，最终返回根节点的深度，即为二叉树的最大深度。

优化后代码（极简高效，注释易懂）

/** * Definition for a binary tree node. * public 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; * } * } */ class Solution { // 主方法：直接调用深度计算方法，返回二叉树最大深度 public int maxDepth(TreeNode root) { return getDepth(root); } // 辅助方法：后序遍历计算单个节点的深度 private int getDepth(TreeNode node) { // 终止条件：空节点深度为0 if (node == null) { return 0; } // 左：递归计算左子树深度 int leftDepth = getDepth(node.left); // 右：递归计算右子树深度 int rightDepth = getDepth(node.right); // 中：当前节点深度 = 左右子树最大深度 + 1（包含自身） int currentDepth = Math.max(leftDepth, rightDepth) + 1; return currentDepth; } }

✨ 亮点拉满！后序遍历天生就适合这种“先算子树、再算当前节点”的场景，代码极简无冗余，时间复杂度O(n)（每个节点只遍历一次），空间复杂度O(h)（h是树的高度），面试写这个，面试官都得夸你思路清晰！

总结

最后来个小总结，帮大家划重点👇

两道题直接覆盖二叉树「遍历」和「深度计算」两大核心考点，新手必刷：

1. 中序遍历：统一迭代法YYDS，解决递归栈溢出，模板化代码可复用；

2. 最大深度：后序递归解法极简，逻辑清晰，面试直接抄作业。

建议大家动手敲一遍代码，理解null标志位和后序遍历的核心逻辑，搞定这两道题，后续二叉树相关题目，你就能快速找到思路，轻松拿捏啦～

1. 中序遍历：统一迭代法解决递归栈溢出问题，模板化代码可复用；

2. 最大深度：后序递归解法极简高效，逻辑清晰易理解。

建议大家动手敲一遍代码，理解null标志位和后序遍历的核心逻辑，后续遇到二叉树相关题目，就能快速找到解题思路啦～