【Java实习面试算法冲刺】二叉树

第6类题型：二叉树

为什么二叉树题你觉得模板背熟了，一到面试还是容易递归写乱

很多同学刷二叉树题时，会觉得“树题不就是前中后序遍历、再加一个层序遍历吗”。这句话只对了一半。真正到了面试现场，二叉树题的难点不是遍历名字，而是你能不能先把问题拆清楚：这题到底该用 DFS 还是 BFS，递归函数返回的到底是什么，当前这一层又在做什么。

这类题最容易暴露出几种问题：

• 你知道要递归，但没定义清楚函数返回值，写着写着就乱了。
• 你会背 Queue + size，却说不清为什么必须先固定当前层节点数。
• 你把树题理解成“套模板”，结果一遇到镜像、路径、子树信息合并就开始发虚。

如果你现在处在“基础树题能做一点，但面试官一追问递归含义就卡住”的阶段，这一类题特别值得单独梳理。读完这篇，你至少要把 3 件事练熟：先判断该用 DFS 还是 BFS、先定义递归函数返回什么、能在面试里解释每一层或每棵子树到底在返回什么信息。

文章目录

• 第6类题型：二叉树
• • 为什么二叉树题你觉得模板背熟了，一到面试还是容易递归写乱
  • 1. 核心知识点
  • • 动画辅助理解：递归函数先定义返回值
  • 2. 这类题在面试里考什么
  • 3. 高频题清单
  • 4. 这类题最容易犯的 3 个错误
  • 5. 代表题精讲 1
  • • 题目
    • 思路
    • Java 代码
    • 复杂度
    • 边界提醒
    • 如果这是面试现场，你可以这样说
  • 6. 代表题精讲 2
  • • 题目
    • 思路
    • Java 代码
    • 复杂度
    • 边界提醒
    • 如果这是面试现场，你可以这样说
  • 7. 其余题模板与关键片段
  • • [`104. 二叉树的最大深度`](https://leetcode.cn/problems/maximum-depth-of-binary-tree/)
    • [`226. 翻转二叉树`](https://leetcode.cn/problems/invert-binary-tree/)
  • 8. 树题先判断什么
  • 9. 错题本记录方式
  • 10. 面试前 3 分钟速记
  • 11. 最后总结：树题先想清返回什么，再决定怎么遍历

1. 核心知识点

二叉树题的第一步不是写代码，而是先判断题目更适合：

• DFS 递归
• BFS 层序遍历

如果题目问：

• 深度、高度、路径、左右子树关系，优先想 DFS。
• 一层一层处理、最短步数、逐层输出，优先想 BFS。

树题最容易混乱的地方在于“递归函数到底返回什么”。你必须先讲清楚返回值定义，再写递归。

层序遍历模板：

Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}

动画辅助理解：递归函数先定义返回值

二叉树题最适合先用“子树向父节点返回信息”这件事建立直觉。你可以先打开本地动画页：

二叉树：递归函数返回值分步动画

这个动画最值得盯住的是 4 步：

• 先定义 dfs(root) 到底返回什么，比如深度、高度、最大贡献值。
• 进入根节点时，先判断空节点的基础返回值。
• 再递归左右子树，把子问题拆给 root.left 和 root.right。
• 最后把左右子树返回的信息合并成当前节点的答案，再交还给父节点。

拿“最大深度”举例，节点 3 的答案并不是凭空得来的，而是靠左右子树一步步回传：

这就是树题里最常见的思维：子树先算好，再由父节点做合并。

2. 这类题在面试里考什么

二叉树题考的不是背遍历顺序，而是你是否真正理解递归和层序这两套思维。

面试官通常会看：

• 你能不能先判断用 DFS 还是 BFS。
• 你递归函数的含义是否清楚。
• 你是否会写终止条件。
• 你能不能解释每一层处理逻辑。

真正的区分度不在“会不会写遍历”，而在“你能不能把当前节点、左右子树、当前层队列这几个角色之间的关系讲明白”。

3. 高频题清单

4. 这类题最容易犯的 3 个错误

5. 代表题精讲 1

题目

101. 对称二叉树

思路

这题不是简单地比较左右子树值是否相等，而是比较两棵子树是否镜像对称。

镜像对称意味着：

• 根值相等。
• 左子树的左节点等于右子树的右节点。
• 左子树的右节点等于右子树的左节点。

因此可以写一个递归函数 isMirror(left, right)。

Java 代码

class Solution {
public boolean isSymmetric(TreeNode root) {
return isMirror(root.left, root.right);
}

private boolean isMirror(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null) {
return false;
}
if (left.val != right.val) {
return false;
}
return isMirror(left.left, right.right)
&& isMirror(left.right, right.left);
}
}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(h)，h 为树高

边界提醒

这题最关键的边界不是数值相不相等，而是空节点情况。left == null && right == null 时应该返回 true，因为两边都空说明当前位置仍然对称；只要一边空、一边不空，就必须立刻返回 false。

如果这是面试现场，你可以这样说

这题我会把它看成“两棵树是否镜像对称”的递归比较题。对于两个节点 left 和 right，只有在它们值相等、并且 left.left 对应 right.right、left.right 对应 right.left 时，当前结构才对称。所以递归函数本质是在检查镜像关系，而不是单纯检查左右子树各自是否对称。

6. 代表题精讲 2

题目

102. 二叉树的层序遍历

思路

这题是 BFS 的标准模板。关键点是使用队列按层推进，并且在每一轮开始时记录当前层节点数 size。

为什么要记录 size：因为队列会在遍历当前层时不断加入下一层节点。如果不先固定这一层的节点数，就无法分出层次。

比如当前队列里是 [3]，这一轮的 size = 1，说明这一层只有根节点。处理完 3 之后，才把 9 和 20 放进队列。下一轮开始时，队列变成 [9, 20]，此时 size = 2，就知道这是下一层要处理的两个节点。

Java 代码

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}

Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);

while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(level);
}

return result;
}
}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

边界提醒

这题最容易忽略的边界是空树。root == null 时，应该直接返回空列表，而不是把 null 放进队列里继续处理。另一个常见错误是没先记 size，结果把下一层节点也混进当前层一起处理了。

如果这是面试现场，你可以这样说

这题适合 BFS。因为题目要求按层输出，所以我会用队列维护当前层待处理节点，并在每一轮开始时先记录队列长度 size，这样就能把同一层节点完整取出来，再把下一层节点放进队列。整个过程相当于标准的层序遍历模板。

7. 其余题模板与关键片段

104. 二叉树的最大深度

典型 DFS：

if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;

这题最重要的不是公式，而是你要明确：maxDepth(root) 返回的是“以当前节点为根的这棵子树最大深度”。

226. 翻转二叉树

递归交换左右子树：

TreeNode temp = root.left;
root.left = root.right;
root.right = temp;

这类题的重点是先处理当前节点，再递归左右，还是先递归再交换。只要你能说明当前步骤在做什么，树题就不容易乱。

8. 树题先判断什么

真正写代码前，你可以先问自己 4 个问题：

这 4 个问题回答清楚，树题大部分混乱都能提前避开。

9. 错题本记录方式

树题建议重点记录：

• 我为什么判断这题该用 DFS / BFS。
• 递归函数返回值到底代表什么。
• 终止条件漏了哪种空节点情况。
• 层序遍历时是否忘了固定当前层大小。

10. 面试前 3 分钟速记

• 树题先分 DFS 和 BFS。
• DFS 先定义递归函数返回什么。
• BFS 记住 Queue + size。
• 对称树是“镜像比较”，不是“左右各自比较”。
• 最大深度、翻转二叉树是最基础的树题模板。

11. 最后总结：树题先想清返回什么，再决定怎么遍历

如果你只能记住一句话，那就是：二叉树题最怕的不是代码长，而是你没先想清“当前节点要从子树拿什么信息，或者当前层要处理什么信息”。

面试时你只要能按这个顺序去讲，思路就会稳定很多：

这样你不只是会背树题模板，而是真的开始掌握树题的共性。

上期速递：【Java实习面试算法冲刺】栈、队列与单调栈 感谢阅读，记得点赞、关注、收藏，欢迎各位评论区交流！！！