第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。树题最容易混乱的地方在于“递归函数到底返回什么”。你必须先讲清楚返回值定义再写递归。层序遍历模板QueueTreeNodequeuenewArrayDeque();queue.offer(root);while(!queue.isEmpty()){intsizequeue.size();for(inti0;isize;i){TreeNodenodequeue.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的答案并不是凭空得来的而是靠左右子树一步步回传节点左子树返回右子树返回当前节点返回什么叶子节点9001节点20112根节点3123这就是树题里最常见的思维子树先算好再由父节点做合并。2. 这类题在面试里考什么二叉树题考的不是背遍历顺序而是你是否真正理解递归和层序这两套思维。面试官通常会看你能不能先判断用 DFS 还是 BFS。你递归函数的含义是否清楚。你是否会写终止条件。你能不能解释每一层处理逻辑。真正的区分度不在“会不会写遍历”而在“你能不能把当前节点、左右子树、当前层队列这几个角色之间的关系讲明白”。3. 高频题清单题目来源难度高频属性101. 对称二叉树LeetCode 热题 100Easy面试高频104. 二叉树的最大深度LeetCode 热题 100Easy高频102. 二叉树的层序遍历LeetCode 热题 100Medium高频 Medium226. 翻转二叉树面试经典 150Easy基础高频4. 这类题最容易犯的 3 个错误递归函数含义没定义清楚写着写着就乱了。BFS 层序遍历不会用size控制一层。把“前中后序遍历模板”当成理解树题的全部。5. 代表题精讲 1题目101. 对称二叉树思路这题不是简单地比较左右子树值是否相等而是比较两棵子树是否镜像对称。镜像对称意味着根值相等。左子树的左节点等于右子树的右节点。左子树的右节点等于右子树的左节点。因此可以写一个递归函数isMirror(left, right)。Java 代码classSolution{publicbooleanisSymmetric(TreeNoderoot){returnisMirror(root.left,root.right);}privatebooleanisMirror(TreeNodeleft,TreeNoderight){if(leftnullrightnull){returntrue;}if(leftnull||rightnull){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{publicListListIntegerlevelOrder(TreeNoderoot){ListListIntegerresultnewArrayList();if(rootnull){returnresult;}QueueTreeNodequeuenewArrayDeque();queue.offer(root);while(!queue.isEmpty()){intsizequeue.size();ListIntegerlevelnewArrayList();for(inti0;isize;i){TreeNodenodequeue.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. 二叉树的最大深度典型 DFSif(rootnull)return0;returnMath.max(maxDepth(root.left),maxDepth(root.right))1;这题最重要的不是公式而是你要明确maxDepth(root)返回的是“以当前节点为根的这棵子树最大深度”。226. 翻转二叉树递归交换左右子树TreeNodetemproot.left;root.leftroot.right;root.righttemp;这类题的重点是先处理当前节点再递归左右还是先递归再交换。只要你能说明当前步骤在做什么树题就不容易乱。8. 树题先判断什么真正写代码前你可以先问自己 4 个问题这题更像 DFS 递归还是 BFS 层序遍历。如果是递归我的函数返回值到底代表什么。如果是 BFS我这一层怎么和下一层分开。空节点出现时我的基础返回值应该是什么。这 4 个问题回答清楚树题大部分混乱都能提前避开。9. 错题本记录方式树题建议重点记录我为什么判断这题该用 DFS / BFS。递归函数返回值到底代表什么。终止条件漏了哪种空节点情况。层序遍历时是否忘了固定当前层大小。10. 面试前 3 分钟速记树题先分 DFS 和 BFS。DFS 先定义递归函数返回什么。BFS 记住Queue size。对称树是“镜像比较”不是“左右各自比较”。最大深度、翻转二叉树是最基础的树题模板。11. 最后总结树题先想清返回什么再决定怎么遍历如果你只能记住一句话那就是二叉树题最怕的不是代码长而是你没先想清“当前节点要从子树拿什么信息或者当前层要处理什么信息”。面试时你只要能按这个顺序去讲思路就会稳定很多这题更适合 DFS 还是 BFS。递归函数返回什么或者队列当前层代表什么。空节点的基础情况怎么处理。当前节点是负责合并子树信息还是负责把下一层节点推进队列。这样你不只是会背树题模板而是真的开始掌握树题的共性。上期速递【Java实习面试算法冲刺】栈、队列与单调栈感谢阅读记得点赞、关注、收藏欢迎各位评论区交流
