Hot 100 刷到 41-50恰好卡在一个很微妙的节点上。前面 40 道题刚把数组、哈希、双指针、滑动窗口、栈和链表轮了一遍后面马上要摸到动态规划的门槛而中间这十道题几乎清一色是二叉树。说实话这个区段在 Hot 100 里特别容易被低估单看每一道都不算难但把它们串在一起恰好构成了一整套二叉树的基础能力闭环——递归、DFS、BFS、二叉搜索树性质、祖先查找、结构变换全都在里面了。这篇文章不打算一道题一道题平铺直叙地念题解那太浪费了。我想按自己的刷题顺序把这十道题重新拆成几个组遍历模板、结构判断、搜索树应用、综合变换然后告诉你每组的代码骨架怎么背、易错点在哪、哪些地方是面试官喜欢深挖的。无论你是刚刷完链表准备过渡到树还是二刷想彻底整理一遍树专题这份笔记都能帮你省下不少时间。1. 这十道题到底在考什么二叉树专题的承重墙1.1 题目分布与内在逻辑以我手头这份 Hot 100 的常见顺序为例41-50 这十道题大概是这样的题号常见顺序题目核心考点41二叉树的中序遍历递归模板、迭代栈、二叉树遍历基本功42二叉树的最大深度DFS 递归、BFS 层高43对称二叉树镜像结构判断、递归思维44二叉树的直径后序遍历、全局答案统计45二叉树的层序遍历BFS 模板、按层收集46将有序数组转换为二叉搜索树二分构建、平衡 BST47验证二叉搜索树BST 性质、区间传递48二叉搜索树中第 K 小的元素中序遍历应用、剪枝49二叉树的最近公共祖先后序递归、状态合并50二叉树展开为链表前序顺序、原地改造即使你手里的 Hot 100 顺序和我这份有个别出入也没关系——核心题目就这么多二叉树的高频考点也基本被这十道题覆盖完了。你会发现这十道题不是孤立存在的它们之间有一条很清晰的递进线先会用三种遍历方式走遍二叉树然后能用递归判断结构、统计路径类指标接着进入搜索树这类有特殊性质的树最后综合处理祖先查询和链表化这种复杂变换。1.2 为什么说这是递归能力的试金石二叉树是练习递归最好的素材没有之一。数组和链表的递归多少带着点别扭因为它们的线性结构用循环写更自然但树天然就是递归定义的——一棵树的左子树还是树右子树还是树。处理一个节点的方式和处理整棵树的方式完全一样这就是递归三要素最直观的演示入参与返回值设计只处理一棵子树时入参是根节点返回的是这棵子树的某种结果高度、布尔值、列表等。终止条件绝大多数树题递归的终止条件都是root null空树本身就是最小子问题。单层逻辑确定当前节点要做什么左右子树的结果怎么合并。我自己带新人刷题的时候常说一句话树的递归像处理一组俄罗斯套娃你只需要把手上这一个套娃正确打开剩下的套娃交给递归去开。这句话虽然简单但很多人写不出树题代码恰恰是卡在当前层到底要返回什么上。1.3 适合谁来刷、怎么刷更高效这组题适合两类人。第一类是刚开始接触树的刷题新手从第 41、42 题入手先把递归和迭代两种写法都跑通不要急着刷难题第二类是准备面试想系统整理树专题的开发者这十道题按今天的分组刷两遍基本能应付大部分公司的二叉树面试题。我建议的刷题顺序不是按题号死磕而是按模板成组刷先刷中序遍历和最大深度建立递归直觉再把迭代版本也写熟。再刷对称二叉树和树的直径体会递归返回值和全局答案是两回事。接着一口气做有序数组转 BST、验证 BST、第 K 小元素这三道题共用同一套性质BST 中序遍历就是升序数组。最后攻最近公共祖先和展开为链表这两道综合题对上一步的递归能力要求最高。二刷的时候有个很有效的训练方式把递归写法强制改成迭代写法或者反过来把迭代写法改成递归。同一道题用两种方式各写一遍你对系统栈的理解会深很多后面碰到递归层数太深导致栈溢出时也知道怎么手动用栈去替代。2. 深度遍历的三种模板中序、深度与直径2.1 中序遍历一份模板走天下二叉树的中序遍历是 41-50 里最基础的一道也是后面验证 BST和第 K 小元素的解题地基。所谓中序就是处理顺序是 左子树 → 根节点 → 右子树。先看递归写法这个非常短class Solution { public ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); dfs(root, res); return res; } private void dfs(TreeNode node, ListInteger res) { if (node null) return; dfs(node.left, res); res.add(node.val); dfs(node.right, res); } }递归写法一般没太多坑但面试时经常会追加一句你写个迭代版本看看。迭代中序遍历是很多人的老大难本质是用显式栈模拟系统调用栈class Solution { public ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); DequeTreeNode stack new ArrayDeque(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { while (cur ! null) { stack.push(cur); cur cur.left; } cur stack.pop(); res.add(cur.val); cur cur.right; } return res; } }这个迭代模板的记忆口诀是能往左走就往左走走不动了就弹栈访问然后转向右子树。你可以把它理解为先把左边界全部压进栈之后每弹出一个节点就尝试处理它的右子树。很多人在迭代中序上栽跟头是因为没理解cur cur.right这行——即使当前节点没有右子树cur变成null也没关系因为外层循环的!stack.isEmpty()还能继续撑着直到栈也空才算完。2.2 最大深度理解高度到底怎么算二叉树的最大深度指的是从根节点到最远叶子节点的最长路径上的节点数。递归解法几乎是一行代码class Solution { public int maxDepth(TreeNode root) { if (root null) return 0; return 1 Math.max(maxDepth(root.left), maxDepth(root.right)); } }这里面的关键是maxDepth(root)等于1 max(左子树深度, 右子树深度)。为什么要加 1因为当前节点本身占了 1 个深度。这看起来简单但它实际上是一个很重要的思维模型——子树的结果向上合并的时候不能忘记当前层贡献的那份。最大深度也可以用 BFS 来写层序遍历完整棵树队列循环了几轮深度就是几class Solution { public int maxDepth(TreeNode root) { if (root null) return 0; DequeTreeNode q new ArrayDeque(); q.offer(root); int depth 0; while (!q.isEmpty()) { int size q.size(); for (int i 0; i size; i) { TreeNode node q.poll(); if (node.left ! null) q.offer(node.left); if (node.right ! null) q.offer(node.right); } depth; } return depth; } }面试时我更推荐先说递归写法然后再补一句BFS 也可以统计每层加一。两种都能写出来说明你对 DFS 和 BFS 的底层逻辑都是真的理解而不是只背了一个模板。2.3 二叉树的直径全局答案与递归返回值要分开二叉树的直径这道题第一次做的人十有八九会懵。题目问的是任意两个节点之间路径长度边数的最大值这个最大值不一定穿过根节点。我的解法是后序遍历每到一个节点都算一下经过这个节点的最长路径用一个全局变量更新答案class Solution { int ans 0; public int diameterOfBinaryTree(TreeNode root) { dfs(root); return ans; } private int dfs(TreeNode node) { if (node null) return 0; int left dfs(node.left); int right dfs(node.right); ans Math.max(ans, left right); return Math.max(left, right) 1; } }这道题我当年踩过一个很经典的坑把ans的更新写成left right 1。你想想left和right分别代表左、右子树向下最多能走几条边那么经过当前节点的最长路径是left right条边不是left right 1。如果非要按节点数算那才是left right 1但 LeetCode 这道题明确规定是边数。另一个值得注意的细节递归函数返回的是从当前节点出发往下的最大边数也就是max(left, right) 1而ans记录的是全局最长路径两者不是同一个东西。很多人把返回值和全局答案搞混写着写着就乱套。记住这句递归的返回值是给父节点用的全局答案是自己偷偷更新的。这个思维在后面很多题里都会反复出现。3. 层序遍历与结构判断BFS 的正确姿势3.1 层序遍历模板size 变量是分层的命根子层序遍历的题目要求按层返回结果也就是[[第一层], [第二层], ...]这样的结构。BFS 配合队列是标准解法class Solution { public ListListInteger levelOrder(TreeNode root) { ListListInteger res new ArrayList(); if (root null) return res; DequeTreeNode q new ArrayDeque(); q.offer(root); while (!q.isEmpty()) { int size q.size(); ListInteger level new ArrayList(); for (int i 0; i size; i) { TreeNode node q.poll(); level.add(node.val); if (node.left ! null) q.offer(node.left); if (node.right ! null) q.offer(node.right); } res.add(level); } return res; } }这个模板最大的考点就是int size q.size()这一行。为什么必须在 for 循环前把当前层的节点数固定下来因为队列是一个动态结构你在遍历当前层的过程中已经在往队列尾部添加下一层的节点了。如果 for 循环的终止条件直接写成i q.size()每次q.size()都在变大导致当前层会把下一层的节点也一并 poll 出来结果全部混在一起根本分不出层。我自己的习惯是取完size之后在 for 循环里用size而不是再碰q.size()。这个习惯能帮你秒杀一堆层序变体题比如自底向上层序遍历结果反转即可、锯齿形遍历加一个level % 2 0判断是否反转。3.2 对称二叉树比较的是结构不是单个节点判断一棵二叉树是否轴对称递归写法的核心是比较两棵子树是否为镜像。注意这里传入的对比对象是root.left和root.right两个节点而不是在单个节点上做判断class Solution { public boolean isSymmetric(TreeNode root) { if (root null) return true; return compare(root.left, root.right); } private boolean compare(TreeNode left, TreeNode right) { if (left null right null) return true; if (left null || right null) return false; return left.val right.val compare(left.left, right.right) compare(left.right, right.left); } }这里容易忽略的是递归比较的方向外侧要和外侧比内侧要和内侧比。也就是left.left对应right.rightleft.right对应right.left。我第一次刷的时候写成了compare(left.left, right.left)结果怎么跑都是错的——那是比较两棵子树完全相等而不是镜像对称。递归写法之外面试官还喜欢让你写迭代版本。迭代思路是初始化一个队列先同时放入root.left和root.right之后每次取出两个节点比较再把left.left, right.right成对放入再把left.right, right.left成对放入。成对取出、成对入队只要有一次值不相等直接返回 false。3.3 空指针问题树题最大的隐形杀手刷树题报NullPointerException是家常便饭而且报错位置往往很隐蔽。核心原因就一条对null节点直接调用了.val或.left。我总结了一个小原则凡是传入的节点可能为null要么先判空再访问要么干脆把null当作递归的合法状态。以对称二叉树的递归为例compare方法必须先处理两个都为空的场景再处理一个为空另一个非空的场景最后才敢比较left.val和right.val。顺序一旦反了空指针就会冒出来。经验之谈树题里的if (node null)不只是一个防御性判断它往往是递归的终止条件。写递归前先想清楚空节点在这道题里意味着什么能帮你避开一半以上的 bug。4. 二叉搜索树专题性质本身就是答案4.1 将有序数组转换为二叉搜索树取中点就是平衡的保证这道题的题目要求构建一棵高度平衡的二叉搜索树也就是每个节点的左右子树高度差不超过 1。思路非常直接既然数组有序就取数组的中间位置作为根节点左半部分递归构建左子树右半部分递归构建右子树。这样左右子树的节点数量差不会超过 1高度平衡自然就保证了。class Solution { public TreeNode sortedArrayToBST(int[] nums) { return build(nums, 0, nums.length - 1); } private TreeNode build(int[] nums, int left, int right) { if (left right) return null; int mid left (right - left) / 2; TreeNode root new TreeNode(nums[mid]); root.left build(nums, left, mid - 1); root.right build(nums, mid 1, right); return root; } }这个解法看起来平淡无奇但有一个细节值得说mid的计算我写的是left (right - left) / 2而不是(left right) / 2。虽然数组下标不会像整数溢出那样夸张但这是一种好的编码习惯——同理在二分查找里这个写法能直接避免left right溢出。另外当数组长度是偶数时取左中点还是右中点都可以都能构建出高度平衡的 BST。LeetCode 的判题通常两种都接受。如果面试官追问为什么取中点就能保证平衡你可以答左半边和右半边的元素个数差最多为 1那么构建出来的子树高度差也最多为 1。4.2 验证二叉搜索树很多人的第一个错误解法这道题的错误解法极具代表性我几乎每次带人都能看到// 错误示范只比较当前节点和左右孩子的值 if (root.left.val root.val) return false; // 不对而且还没判空 if (root.right.val root.val) return false; return isValidBST(root.left) isValidBST(root.right);这个写法的问题在于它只验证了父节点大于左孩子、小于右孩子但 BST 的定义要求的是左子树所有节点都小于根右子树所有节点都大于根。举例来说根节点是 5左孩子是 3左孩子的右孩子是 66 大于 5 却藏在左子树里只比较父子节点的写法就发现不了。正确的递归需要把取值范围一路传递下去class Solution { public boolean isValidBST(TreeNode root) { return valid(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean valid(TreeNode node, long low, long high) { if (node null) return true; if (node.val low || node.val high) return false; return valid(node.left, low, node.val) valid(node.right, node.val, high); } }为什么用Long.MIN_VALUE和Long.MAX_VALUE而不是Integer.MIN_VALUE和Integer.MAX_VALUE因为 BST 的节点值本身就是int范围如果用int的极值作为初始边界万一某个节点值正好等于Integer.MIN_VALUE就会在node.val low这个判断里被误杀。还有一种更优雅的写法是利用中序遍历。BST 的中序遍历结果是严格递增的序列所以只要在中序遍历过程中记录前一个节点的值检查当前值是否大于前一个值即可。这也是把中序遍历模板活用的典型场景我已经不止一次在面试连环问里遇到它了。4.3 第 K 小的元素中序遍历就是升序数到 K 就行BST 一个最可爱的性质是对 BST 做中序遍历得到的就是所有元素的升序排列。所以找第 K 小最朴素的想法就是中序遍历数到第 K 个直接返回。用递归实现class Solution { int count; int result; public int kthSmallest(TreeNode root, int k) { count k; dfs(root); return result; } private void dfs(TreeNode node) { if (node null) return; dfs(node.left); count--; if (count 0) { result node.val; return; } dfs(node.right); } }注意count--放在访问根节点的时候正好对应左 → 根 → 右的处理顺序。如果不想写成员变量也可以用迭代版中序遍历边遍历边递减 kk 减到 0 时弹出的节点就是要找的答案class Solution { public int kthSmallest(TreeNode root, int k) { DequeTreeNode stack new ArrayDeque(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { while (cur ! null) { stack.push(cur); cur cur.left; } cur stack.pop(); if (--k 0) return cur.val; cur cur.right; } return -1; } }这道题的知识点扩展是如果一棵树会被高频查询第 K 小元素中序遍历的 O(n) 复杂度就不太够用了。这时可以在每个节点上额外维护左子树的节点数利用 BST 性质和左子树大小快速定位到目标节点把单次查询降到 O(log n)。这个进阶方案很多面试官喜欢追问提前了解没坏处。4.4 最近公共祖先后序递归合并两个子树的状态最近公共祖先LCA可能是这十道题里递归思维最综合的一道。先看代码class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root null || root p || root q) return root; TreeNode left lowestCommonAncestor(root.left, p, q); TreeNode right lowestCommonAncestor(root.right, p, q); if (left ! null right ! null) return root; return left ! null ? left : right; } }这个递归的终止条件很有意思root p || root q时直接返回root。这意味着一个节点也可以被看作它自己的祖先。这正好覆盖了p 是 q 的祖先这种特殊情况——比如 p 就在根节点位置那递归到 root 等于 p 时直接返回最后的结果就是 p。在左右子树都递归完之后可能出现几种情况左右两边都找到了目标节点说明 p 和 q 分别位于当前节点的左右两个子树中当前节点就是它们的公共祖先。只有左边返回了非空节点说明 p 和 q 都在左子树里左边返回的那个节点就是答案。只有右边返回了非空节点同理。这其实就是一种后序遍历先递归处理完左右子树再根据左右子树的结果决定当前节点该返回什么。当你能熟练写出这道题的递归逻辑再遇到判断一棵树是否是另一棵树的子树、树中两节点的距离这类变形题思路会顺畅很多。5. 展开为链表与结构变换前序顺序的多种落地方式5.1 二叉树展开为链表收集再重连是最容易理解的方法这道题要求按照前序遍历的顺序把二叉树展开成一条只有右子节点的链表。最简单也最容易在面试中先给出的解法是先前序遍历收集所有节点到一个列表再遍历列表把每个节点的 left 置空、right 指向下一个节点class Solution { public void flatten(TreeNode root) { ListTreeNode list new ArrayList(); preorder(root, list); for (int i 0; i list.size() - 1; i) { TreeNode node list.get(i); node.left null; node.right list.get(i 1); } } private void preorder(TreeNode node, ListTreeNode list) { if (node null) return; list.add(node); preorder(node.left, list); preorder(node.right, list); } }这个方法的时间复杂度是 O(n)空间复杂度也是 O(n)。面试时先说这种解法能证明你思路清晰但通常面试官会追一句能不能 O(1) 空间完成也就是在原树上原地改造不借助额外列表。5.2 原地展开找左子树最右节点原地展开的经典做法像一种螺旋进程每到一个节点如果它有左子树就把左子树中最右的节点找出来然后把当前节点的右子树接到这个最右节点的右边再把左子树整体移到右边左指针置空最后移动到下一个右节点继续处理。代码是这样class Solution { public void flatten(TreeNode root) { TreeNode cur root; while (cur ! null) { if (cur.left ! null) { TreeNode last cur.left; while (last.right ! null) { last last.right; } last.right cur.right; cur.right cur.left; cur.left null; } cur cur.right; } } }这个方法的本质是什么前序遍历的顺序是根 → 左子树 → 右子树那么当根节点把左子树移到右侧后原本的右子树必须跟在左子树所有节点之后。左子树在前序里最后一个被访问到的节点就是左子树里的最右节点所以把右子树接到这个位置前序顺序才不会乱。我刷这道题的时候犯过一个很隐蔽的错误在while (cur ! null)的外层循环里cur cur.right之后没有检查新的右节点是否为空就开始下一轮导致空指针。后来习惯先调试一遍单链化的树再提交就稳了。这道题的原地解法是很多大厂二面的现场追踪题强烈建议自己动手把执行过程完整走一遍。5.3 结构变换类题目通用的思维模板整理一下 49 和 50 这两道综合题能提炼出一套处理树结构变换的通用思路先确定遍历方式需要先知道子树信息的用后序需要按某种顺序重排的用前序或中序。分清楚返回值和副作用LCA 的递归返回值是子树的查找结果flatten 的原地修改则是直接操作树结构不依赖返回值。画例子别直接在空代码上硬想拿一棵三层的小树手推一遍递归的执行过程比看十遍题解都有用。说真的很多人刷树题感觉吃力不是因为不懂算法而是因为对一棵树的递归展开过程没有画面感。我每次带新人都会让他们做一件事找一张纸画一棵三层二叉树然后照着代码一行一行模拟stack的变化或者模拟递归栈的进出顺序。做完一两次后面大部分树题都能自己啃下来了。6. 刷题实录易错点与排查清单6.1 高频报错速查表刷这一批题的时候我把自己和身边朋友踩过的坑整理成了一张速查表每次卡住了就对着表查一遍效率很高症状常见原因解决思路空指针异常没判null直接访问node.val/node.left把node null当作递归终止条件先判空再操作递归栈溢出树退化成链状递归深度过大改为显式栈迭代或考虑 Morris 遍历中序层序遍历结果混在一起for 循环里用q.size()作为终止条件循环前先int size q.size()固定当前层大小直径结果偏大或偏小混淆边数和节点数直径用left right递归返回用max(left, right) 1BST 验证误判只比较父子节点没有传递区间用(low, high)区间递归或中序遍历看递增第 K 小结果不对没有利用中序或 count 位置放错count 减一放在访问根节点时而不是进入左子树时LCA 返回 null没有考虑 p 或 q 本身就是祖先的情况终止条件加上 root pflatten 死循环原地修改时右指针接错位置找到左子树最右节点把原右子树接到它的右侧重要提示第 K 小元素这道题如果在递归中用了成员变量count和result单次调用没问题但同一个Solution实例在多线程环境下就会有状态竞争。面试时如果讨论到这个问题可以直接提出改成迭代版或参数传递展示出你对状态管理的敏感度。6.2 递归转迭代的通法把递归代码改成迭代背后的核心就是手动用栈模拟系统栈。不同的遍历方式入栈顺序差异很大前序迭代根先入栈弹出访问后先压右孩子再压左孩子因为栈是后进先出左孩子后压会先弹出。中序迭代先一路把左边界压栈弹出访问后转向右子树。这是第 41 题的模板。后序迭代比较别扭。取巧的方式是先用根 → 右 → 左的类前序变体遍历一遍再把结果反转追求标准就用双栈法或lastVisited标记法。我个人认为中序迭代模板是必须背熟的因为它在 BST 类题目中出现频率极高验证 BST、第 K 小元素、BST 转双向链表全都能用它。前序和后序的迭代属于进阶能力能写出来是加分项用递归解决也不丢分。关键是要知道两种写法的复杂度本质上一样面试时先用自己有把握的方式再额外提一句我也可以改成迭代主动权就回到了你手里。6.3 刷完这十道题之后往哪走把 41-50 这组题吃透之后你的树基础就算立住了。接下来 Hot 100 后段会进入动态规划的密集区我最早看到热搜词里出现hot100 动态规划的时候专门回头重新整理过树的递归框架——因为树的递归和 DP 的记忆化搜索在思维上是承接的都是把大问题拆成子问题先解决子问题再合并结果。树天然没有重叠子问题所以用递归很轻松而 DP 之所以需要备忘录或 DP 表就是因为子问题会出现重复计算。这个衔接点很多人没意识到。刷树题练出来的分解 合并直觉其实是进入 DP 领域之前最好的一层铺垫。我自己的经验是先老老实实把这十道树的递归代码手写三遍以上再去碰打家劫舍、最长递增子序列这类 DP 题你会发现自己对状态定义、转移方程的理解明显顺畅很多。树的递归是看得见的状态转移DP 只是多了一张表而已。最后分享一个刷题习惯每道树题提交通过之后都回头问自己三个问题——如果树有十万个节点这写法还能过吗如果面试官要求不用递归我写得出来吗这道题的遍历顺序换一下能解决什么变体把这三个问题想清楚刷这一组题的时间才算花在了刀刃上。