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

第6类题型：二叉树

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

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

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

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

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

1. 核心知识点

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

• DFS 递归
• BFS 层序遍历

如果题目问：

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

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

层序遍历模板：

Queue<TreeNode>queue=newArrayDeque<>();queue.offer(root);while(!queue.isEmpty()){intsize=queue.size();for(inti=0;i<size;i++){TreeNodenode=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 个错误

1. 递归函数含义没定义清楚，写着写着就乱了。
2. BFS 层序遍历不会用size控制一层。
3. 把“前中后序遍历模板”当成理解树题的全部。

5. 代表题精讲 1

题目

101. 对称二叉树

思路

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

镜像对称意味着：

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

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

Java 代码

classSolution{publicbooleanisSymmetric(TreeNoderoot){returnisMirror(root.left,root.right);}privatebooleanisMirror(TreeNodeleft,TreeNoderight){if(left==null&&right==null){returntrue;}if(left==null||right==null){returnfalse;}if(left.val!=right.val){returnfalse;}returnisMirror(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 代码

importjava.util.ArrayDeque;importjava.util.ArrayList;importjava.util.List;importjava.util.Queue;classSolution{publicList<List<Integer>>levelOrder(TreeNoderoot){List<List<Integer>>result=newArrayList<>();if(root==null){returnresult;}Queue<TreeNode>queue=newArrayDeque<>();queue.offer(root);while(!queue.isEmpty()){intsize=queue.size();List<Integer>level=newArrayList<>();for(inti=0;i<size;i++){TreeNodenode=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);}returnresult;}}

复杂度

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

边界提醒

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

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

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

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

104. 二叉树的最大深度

典型 DFS：

if(root==null)return0;returnMath.max(maxDepth(root.left),maxDepth(root.right))+1;

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

226. 翻转二叉树

递归交换左右子树：

TreeNodetemp=root.left;root.left=root.right;root.right=temp;

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

8. 树题先判断什么

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

1. 这题更像 DFS 递归，还是 BFS 层序遍历。
2. 如果是递归，我的函数返回值到底代表什么。
3. 如果是 BFS，我这一层怎么和下一层分开。
4. 空节点出现时，我的基础返回值应该是什么。

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

9. 错题本记录方式

树题建议重点记录：

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

10. 面试前 3 分钟速记

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

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

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

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

1. 这题更适合 DFS 还是 BFS。
2. 递归函数返回什么，或者队列当前层代表什么。
3. 空节点的基础情况怎么处理。
4. 当前节点是负责合并子树信息，还是负责把下一层节点推进队列。

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

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