二叉树进阶实战：层序、BST、公共祖先与路径题套路详解

上一篇我们完成了 Hot 100 二叉树部分的打底题：递归和迭代的前中后序遍历、最大深度、翻转、对称、简单路径总和。这批题的特点是单个节点自己能搞定，root.left、root.right、返回值三件套一写，基本就能跑通。到了 part02，情况完全不一样了——我不止一次在评论区看到同一种困惑：同样的遍历模板，为什么刷到层序、验证 BST、最近公共祖先时就突然看不懂答案了？

这篇记录的是我从“会遍历”过渡到“能解中等题”的实战过程，把 Hot 100 里二叉树后半段的题按几条主线串起来讲。它适合两类人：一类是把二叉树简单题刷完、正准备往中等题进阶的读者；另一类是已经刷过一遍、但觉得每道题解法都像新题、找不到共性的读者。读完你应该能自己归纳出套路：层序是一个队列模板套四道题，BST 核心是“中序有序”和“区间约束”，路径类难题多半靠后序遍历的贡献值思想，而重建二叉树不过是“找根 + 分块 + 递归”的重复动作。

1. 从 part01 到 part02：进阶题的四种形态变化

先看一下题目的变化趋势。part01 的经典题，比如翻转二叉树、最大深度，本质上都在问“单棵树节点自己的属性”；你只需要针对当前节点做判断，然后递归处理左右子树，返回值要么是布尔、要么是深度，不会牵扯全局状态。

part02 的题出现了四种新的形态，我按自己的理解把它们分了组。

第一种是“按层处理”。典型代表是层序遍历（102）、之字形遍历（103）、二叉树的右视图（199），还包括一个看起来完全不是树的题：腐烂的橘子（994）。这类题的核心是把“递归式地往下钻”换成“迭代式地横向扫”，队列是这个系列的唯一主角。

第二种是“结构性质验证”。代表是验证二叉搜索树（98）、BST 的中序性质解题（230）、不同的二叉搜索树（96）。这类题已经不是判断“节点自身满不满足条件”，而是要判断“整棵树是否满足一种全局单调性”，很多人的误区就是把局部比较当成全局验证。

第三种是“在树上找路径和公共祖先”。最近公共祖先（236）、路径总和 III（437）、二叉树的直径（543）、二叉树中的最大路径和（124）。这四道题放在一起看特别有意思：它们的解法全是后序遍历，但后序遍历的“返回值”语义完全不同，一个是返回碰头节点，一个是返回子树贡献值，一个是更新全局答案。

第四种是“用遍历序列还原树”。前序 + 中序重建（105）、中序 + 后序重建（106）。这类题的核心是分治，递归过程本身不复杂，复杂的是下标计算，稍不注意就数组越界。

我建议刷 part02 的时候把上面四组分开来打，每组内部连着刷，效果比一道简单一道中等地跳着刷好得多。下面我按这个分组，把每组的核心技巧和踩坑点展开说。

2. 层序遍历一条线：队列模板吃透四种变体

2.1 基础层序遍历的一个模板

层序遍历的标准写法是while (queue 非空)配一个内层for (int i = 0; i < size; i++)。这个size必须在一轮开始时用变量固定住，不能写成i < queue.size()，因为内层 poll 的同时还在 offer 新节点，队列长度会一直变化，导致每层的节点被拆分到多个 list 里。

我一开始写层序时犯过一个挺蠢的错：在 for 循环条件里直接写了queue.size()，结果同一层的节点被分成好几组，测试用例输出完全对不上。后来改成先int size = queue.size()再进入内层循环，这个问题就消失了。这个习惯在 994 腐烂橘子里面一样适用，因为腐烂扩散的“分钟数”就是靠轮数来计时的。

基础层序代码如下：

public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) return res; Queue<TreeNode> queue = new LinkedList<>(); 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); } res.add(level); } return res; }

很多层序变体，本质上只改这个模板的一两行。

2.2 之字形、右视图：都是模板的微调

之字形遍历（103）在模板基础上加一个从左到右、从右到左的切换。如果你每次都在level的头部 insert，写起来简单，但实际复杂度是 O(n^2)，因为数组头部插入需要移动后续元素。更好的做法是用LinkedList当双端队列，奇数层正常 add，偶数层用addFirst，这样每种插入都是 O(1)。如果你用了ArrayList，也可以在收集完一整层之后统一Collections.reverse(level)。

右视图（199）更简单，只收集每一层的最后一个节点。模板里for循环执行完后，node恰好是该层最后一个节点，把它加入结果即可。这道题也可以用 DFS 先走右子树再走左子树、记录深度来做，但面试时 BFS 模板最容易讲清楚。

2.3 从树走到图：腐烂的橘子为什么也归在这一节

994 腐烂的橘子输入是二维矩阵，连二叉树都算不上，但它的算法本质就是“多源 BFS 分层扩散”，和层序遍历是同一个模板。区别有两点：第一，初始不是只有一个根节点，而是要把所有已经烂掉的橘子一次性入队；第二，轮数对应的是分钟数，需要在内层循环结束后才递增。

这题的关键实现细节：统计新鲜橘子数量fresh，每一轮扩散时如果确实感染了新鲜橘子就让fresh--，只有本轮发生了感染才把分钟数加一。全部结束后，如果fresh > 0，说明有新鲜橘子被孤立，返回 -1。

public int orangesRotting(int[][] grid) { int m = grid.length, n = grid[0].length; Queue<int[]> queue = new LinkedList<>(); int fresh = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 2) queue.offer(new int[]{i, j}); else if (grid[i][j] == 1) fresh++; } } if (fresh == 0) return 0; int minutes = 0; int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}}; while (!queue.isEmpty()) { int size = queue.size(); boolean changed = false; for (int i = 0; i < size; i++) { int[] cur = queue.poll(); for (int[] d : dirs) { int nx = cur[0] + d[0], ny = cur[1] + d[1]; if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) { grid[nx][ny] = 2; fresh--; queue.offer(new int[]{nx, ny}); changed = true; } } } if (changed) minutes++; } return fresh == 0 ? minutes : -1; }

当初我刷到这道题时，第一反应是“这不是二叉树，干嘛放 Hot 100 二叉树专题里”。真做了一遍才明白，出题人想借这个题训练“多源起点 + 分层时间戳”这两个层序变体。面试时如果你能主动说一句“这题的 BFS 分层逻辑和树层序是同一个模板”，印象分会好很多。

3. 二叉搜索树的三个高频考点：验证、第K小、计数

3.1 验证 BST 的核心是“区间”，不是“只和孩子比”

验证二叉搜索树（98）大概是二叉树专题里最容易写出“看着对但其实错”的一题。

新手很容易写出这样的逻辑：检查当前节点的左孩子小于当前节点、右孩子大于当前节点，然后递归左右子树。这个写法在绝大多数小用例上是能过的，但在下面这棵树上会翻车：

10 / \ 5 15 / \ 6 20

按局部判断，6 大于 5 但小于 15，没问题；可是 6 在根的右子树里，却小于根的值 10，整棵树不满足 BST 定义。问题出在哪？局部判断只关心父子两代，没有把祖先的约束传递下来。

正确做法是给递归函数传两个边界：当前节点必须落在(low, high)开区间内。左子树收紧上界为当前节点值，右子树收紧下界为当前节点值。这里有个很实用的经验：边界类型要写成long，不能用int，因为题目测试用例会用Integer.MIN_VALUE和Integer.MAX_VALUE作为节点值，如果用 int 写初始边界，第一层判断就直接误判了。

public boolean isValidBST(TreeNode root) { return validate(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean validate(TreeNode node, long low, long high) { if (node == null) return true; if (node.val <= low || node.val >= high) return false; return validate(node.left, low, node.val) && validate(node.right, node.val, high); }

3.2 中序法：BST 的中序遍历必然是严格递增的

BST 的另一个隐藏性质是：中序遍历结果一定是严格递增序列。所以验证 BST 可以转换成“中序遍历过程中检查相邻元素是否严格递增”。

这个解法思路很顺，但实现时有个容易踩的坑：如果你在递归里维护一个prev变量来记录上一个访问的节点值，普通局部变量在每个递归栈帧里是独立的，改完不会影响上一层。需要用成员变量，或者用一个长度为 1 的数组int[] prev来保存状态。很多写 C/C++ 的同学会习惯用引用传参，Java 里没有这个机制，所以要么成员变量，要么包装。

中序法还有一个好处：它天然能扩展到“BST 的第 K 小元素”这类题。230 题、173 题本质都是“中序遍历的惰性版本”。

3.3 第 K 小和 BST 迭代器：一条中序打天下

第 K 小元素（230）最简单的写法就是中序遍历数到第 K 个就返回，时间复杂度 O(n)，在 Hot 100 的难度下完全能过。如果想更深入一点，可以统计左子树节点个数，利用 BST 的有序性做到 O(log n)，但这要求节点结构额外维护子树大小，LeetCode 默认的TreeNode没有这个字段，所以常规解法就是中序。

BST 迭代器（173）就更有意思了。它要求实现hasNext()和next()，平均时间复杂度 O(1)，空间复杂度 O(h)。递归没法做状态保存，所以用显式栈：从根节点开始，把左链一路压栈；每次next()弹出栈顶节点，并把这个节点的右子树的左链继续压栈。这个“左链入栈”的过程，实际上就是在模拟中序递归的调用栈。

class BSTIterator { private Deque<TreeNode> stack = new ArrayDeque<>(); public BSTIterator(TreeNode root) { pushLeft(root); } public int next() { TreeNode node = stack.pop(); pushLeft(node.right); return node.val; } public boolean hasNext() { return !stack.isEmpty(); } private void pushLeft(TreeNode node) { while (node != null) { stack.push(node); node = node.left; } } }

我当初就是把这道题和中序遍历对照着看，才理解“递归展开成栈”是怎么一回事。如果你觉得递归版中序很熟练，但迭代版写不利索，建议用这个题来练手。

3.4 不同的二叉搜索树：这不是构造，是 DP

不同的二叉搜索树（96）问的是“给定 1 到 n，能构造出多少种不同结构的 BST”。注意，它不要求你构造出来，只要求数量，这就决定了解法不是搜索也不是递归构造，而是递推。

设f[n]表示 n 个节点能组成的 BST 数量。选一个节点当根，剩下 n-1 个节点分到左右两边：左边 i-1 个，右边 n-i 个，方案数是f[i-1] * f[n-i]，对所有可能的 i 求和。这就是卡特兰数的递推形式。

public int numTrees(int n) { int[] f = new int[n + 1]; f[0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { f[i] += f[j - 1] * f[i - j]; } } return f[n]; }

这个题和 95 题“不同的二叉搜索树 II”容易混，95 题确实要构造出所有 BST，解法是递归返回List<TreeNode>，把左右子树的结果列表笛卡尔积组合。96 题不需要那样做，一个一维 DP 就结束了。分清这两个题的差异，比刷十道新题更有用。

4. 最近公共祖先：递归从下往上“碰头”的设计思路

4.1 先想清楚递归返回值的语义

最近公共祖先（236）上来你先别纠缠“怎么判断公共祖先”这个宏大的问题，先问自己：这个递归函数到底返回什么？

我的定义是：lowestCommonAncestor(root, p, q)返回“以 root 为根的子树中，p 或 q 的某个最近公共祖先；如果子树里只包含 p 或 q 之一，就返回那个节点；如果都没有，返回 null”。

基于这个语义，递归逻辑非常简洁：

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; }

这个实现最神奇的地方是：如果 p 恰好是 q 的祖先，那么当递归走到 p 这个节点时，root == p直接返回 p，根本不会往下钻。从更高层看，左子树或右子树返回了 p，另一侧返回 null，最终 p 会被一路向上传递到根。这个行为正好是正确答案。

4.2 为什么“从下往上碰头”能保证最近

很多人第一次看到这个题都会想：能不能从根往下扫，找到第一个“左右子树各包含一个目标节点”的节点？这个思路方向是对的，但实现时如果自上而下扫描，每次都要重新遍历子树判断是否包含 p 或 q，复杂度会变成 O(n^2)。

递归实现之所以简洁，是因为它把“判断是否包含”和“找出公共祖先”合并在了同一次后序遍历里。自底向上返回时，第一次出现左右子树都非空的位置，就是最近公共祖先。注意不是“第一个从上往下满足条件的”，而是“自底向上第一个碰头的”，这个顺序保证了“最近”。

回到代码里，最后一行return left != null ? left : right的逻辑是：如果只有一侧返回非空，说明 p 和 q 都在这侧子树里，那这侧返回的节点就是 LCA，原样上抛即可。

4.3 变形：BST 版 LCA 可以更简单

如果树是 BST（235 题），利用值的区间性质可以省掉很多判断。从上往下找第一个“值夹在 p 和 q 之间”的节点，它就是 LCA。这个结论成立的原因也很直接：p 和 q 如果在当前节点两侧，那当前节点就是它们的最近公共祖先，且不需要继续下探。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while (root != null) { if (root.val > p.val && root.val > q.val) root = root.left; else if (root.val < p.val && root.val < q.val) root = root.right; else return root; } return null; }

把这题和 98 题验证 BST 放在一起看，你会发现 BST 的“区间约束”思想到处都是：验证时用区间约束每个节点，求 LCA 时用区间约束定位目标。这俩是同一个硬币的两面。

4.4 扩展思路：记录父节点再反向查找

236 还有一种常见解法：先用一遍遍历把每个节点的父节点存进 HashMap，然后从 p 往上走，沿途标记；再从 q 往上走，遇到的第一个已被标记的节点就是 LCA。这种解法适合“多次查询”的场景，但 Hot 100 默认的单次查询用递归法更干净。

我个人的经验是：递归法虽然简短，但它对“递归返回语义”的要求更高。学这类题时不要只背代码，每次合上答案自己推一遍：如果当前节点是 p，返回 p；如果左空右非空，返回右；如果左右都非空，返回当前——把这四句话对着代码过一遍，比抄十遍都管用。

5. 前序 + 中序重建二叉树：找根、分块、递归的完整推导

5.1 核心原理：前序找根，中序分左右

重建二叉树（105）的原理一句话就能说清：前序遍历的第一个节点一定是根节点；根节点在中序遍历中的位置，把中序序列分成左子树和右子树两段；左子树的长度确定后，前序序列中紧随根节点的那一段恰好就是左子树的前序遍历，剩下的就是右子树的前序遍历。

举个例子，前序是[3, 9, 20, 15, 7]，中序是[9, 3, 15, 20, 7]。前序第一个 3 是根；中序里 3 的左边只有 9，所以左子树只有一个节点；右边是[15, 20, 7]，对应右子树。接着递归处理右子树的前序[20, 15, 7]和中序[15, 20, 7]，根是 20，左子树 15，右子树 7。

整个过程就是三件事：找根、分块、递归。代码实现不同，效率差别主要来自“找根”这一步。

5.2 两种实现：切片法 vs 哈希索引法

最容易写对的是切片法，每层递归直接截出左右子数组，逻辑清晰，但每次截取都要复制数组，时间和空间都不够优雅。更推荐的是哈希索引法：先用一次循环把中序数组的值和下标存入 HashMap，递归时只传边界下标，不复制数组。

class Solution { private Map<Integer, Integer> idxMap = new HashMap<>(); private int[] pre; public TreeNode buildTree(int[] preorder, int[] inorder) { pre = preorder; for (int i = 0; i < inorder.length; i++) idxMap.put(inorder[i], i); return build(0, 0, inorder.length - 1); } private TreeNode build(int preRootIdx, int inLeft, int inRight) { if (inLeft > inRight) return null; TreeNode root = new TreeNode(pre[preRootIdx]); int inRootIdx = idxMap.get(pre[preRootIdx]); int leftLen = inRootIdx - inLeft; root.left = build(preRootIdx + 1, inLeft, inRootIdx - 1); root.right = build(preRootIdx + leftLen + 1, inRootIdx + 1, inRight); return root; } }

这里的关键是leftLen。很多下标错误都出在不知道“左右子树在前序中的分界点不是固定的”，而是要看左子树有多少个节点。

5.3 中序 + 后序重建的对称思维

106 题把前序换成了后序，思路对称：后序遍历的最后一个元素是根。后序序列从后往前看，先是根，再是右子树的根，再是左子树的根，所以递归时先建右子树，再建左子树，右子树的长度决定了左子树的根在后序中的位置。

class Solution { private Map<Integer, Integer> idxMap = new HashMap<>(); private int[] post; public TreeNode buildTree(int[] inorder, int[] postorder) { post = postorder; for (int i = 0; i < inorder.length; i++) idxMap.put(inorder[i], i); return build(post.length - 1, 0, inorder.length - 1); } private TreeNode build(int postRootIdx, int inLeft, int inRight) { if (inLeft > inRight) return null; TreeNode root = new TreeNode(post[postRootIdx]); int inRootIdx = idxMap.get(post[postRootIdx]); int rightLen = inRight - inRootIdx; root.right = build(postRootIdx - 1, inRootIdx + 1, inRight); root.left = build(postRootIdx - rightLen - 1, inLeft, inRootIdx - 1); return root; } }

这个题的坑在“先递归右子树”这一点上。如果按前序重建的习惯先写root.left = build(postRootIdx - 1, inLeft, inRootIdx - 1)，下标会错位。因为postRootIdx - 1指向的是右子树根，不是左子树根。这也是为什么我一直建议：这类题动手写代码前，先在纸上把两棵树的小例子走一遍，把“下一个要处理的节点在后序数组中的下标”算出来，再开始写。

6. 路径类三兄弟：前缀和、单边贡献、全局最大值

6.1 路径总和 III：前缀和哈希

路径总和 III（437）问的是：从任意节点出发向下，路径和等于给定值的路径数量。朴素做法是以每个节点为起点做 DFS，复杂度 O(n^2)，树深时会超时。

优化思路是前缀和。从根到当前节点的路径和记为cur，如果某个更早的前缀和等于cur - targetSum，那么这一段路径的和就是 targetSum。用 HashMap 统计“从根到当前节点路径上，每个前缀和出现了多少次”。因为路径只能向下走，每个节点回溯时要撤销自己的前缀和计数。

class Solution { public int pathSum(TreeNode root, int targetSum) { Map<Long, Integer> prefix = new HashMap<>(); prefix.put(0L, 1); return dfs(root, 0L, targetSum, prefix); } private int dfs(TreeNode node, long cur, int target, Map<Long, Integer> prefix) { if (node == null) return 0; cur += node.val; int cnt = prefix.getOrDefault(cur - target, 0); prefix.put(cur, prefix.getOrDefault(cur, 0) + 1); cnt += dfs(node.left, cur, target, prefix) + dfs(node.right, cur, target, prefix); prefix.put(cur, prefix.getOrDefault(cur, 0) - 1); return cnt; } }

这段代码有两个容易踩的坑。第一，prefix的 key 要声明成Long，因为路径累加和可能超过 int 范围，虽然最终答案只用差值判断，但累加过程可能溢出。第二，递归返回前一定要prefix.put(cur, ... - 1)撤销当前前缀和，否则兄弟子树会把祖先路径的状态误算进去。

6.2 二叉树的直径：单边贡献的思想

二叉树的直径（543）定义是任意两个节点路径上的最大边数。一条直径必然经过某个节点，并且由“该节点左子树的最深深度 + 右子树的最深深度”组成。所以这题本质上是对每个节点求“左右子树高度之和”，取最大值。

后序遍历实现：递归函数返回“当前节点到叶子节点的最大边数”，在每层更新全局答案ans = Math.max(ans, left + right)。注意返回值和答案的差异非常关键——返回值只给父节点贡献一条边的信息，答案在所有节点处取最大。

class Solution { private int ans = 0; public int diameterOfBinaryTree(TreeNode root) { height(root); return ans; } private int height(TreeNode node) { if (node == null) return 0; int left = height(node.left); int right = height(node.right); ans = Math.max(ans, left + right); return Math.max(left, right) + 1; } }

我刚开始做这道题时，总想着“返回子树直径”，结果发现父节点根本没法用。后来意识到：这个题的递归返回值和目标答案不是同一个量，返回值是“子树提供给我上层的单边贡献”，目标答案是在过程中找最大值。理解了这一层，路径类题目基本打通一半。

6.3 最大路径和：负数贡献直接丢弃

最大路径和（124）思路类似，但节点值可能是负数，所以多了一个裁剪逻辑。递归返回“从当前节点出发，向上走能贡献的最大路径和”，这个值如果小于 0，对上层没有任何帮助，直接按 0 处理。全局答案则在每个节点处用node.val + left + right更新。

class Solution { private int ans = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); return ans; } private int dfs(TreeNode node) { if (node == null) return 0; int left = Math.max(0, dfs(node.left)); int right = Math.max(0, dfs(node.right)); ans = Math.max(ans, node.val + left + right); return node.val + Math.max(left, right); } }

这里常见的疑问是：如果左右子树贡献都取了 0，路径会不会“断开”？不会。因为这个返回值只给上层参考，上层可以选择“用这条边”或“不用这条边”。在计算答案时，当前节点拼上左右贡献形成的路径是一条完整路径；在向上传递时，只保留单边最大贡献，这正好保证不会在一条路径里重复使用某个节点两次。

6.4 路径类三兄弟的一页纸总结

把这三道题放在一起看，规律非常明显：

再往下深挖一层，这三道题全都没有“在递归出口处计算答案”，而是在回溯过程中更新全局状态。这是我刷这部分最核心的体会：树的中等题，经常不是“递归到叶子再返回一个值”，而是“递归返回值服务于父节点，答案藏在过程中的某个状态更新里”。

7. 为什么二叉树程序总报运行时错误：七个高频根因与自查顺序

看到热搜里“写二叉树程序时为什么总是报运行时错误”这个关键词，我太有共鸣了。我早期刷二叉树题时，报错频率最高的阶段就是刚离开简单题、开始碰中等题的时候。这里把最常见的根因和排查顺序整理出来。

7.1 空指针：最常见也最容易自查

二叉树程序一半的运行时错误是空指针。要么是root本身为 null，要么是递归过程中某一个子树为 null 但代码没判断。最典型的错误是：

// 错误示例：node 可能为 null public void walk(TreeNode node) { if (node.val == 1) return; walk(node.left); walk(node.right); }

正确的顺序永远是先把node == null放在最前面，再访问node.val或左右子树。这不是风格问题，是能不能跑对的问题。

7.2 递归出口的顺序错了

还有一类是递归出口写得太晚。比如验证 BST 的递归里，先写if (node.val <= low || node.val >= high)再写if (node == null) return true，一旦传入 null 就报错。我的习惯是：任何递归函数第一行先处理空值，再处理业务逻辑，顺序不能反。

7.3 返回值的语义前后不一致

运行时错误不一定是“崩溃”，也可能是答案完全不对。常见原因是递归返回值语义混乱。比如有人在求直径的题里，递归函数既想返回“当前子树直径”又想返回“当前子树高度”，最后父节点拿到的是错误含义的数据，整个答案乱套。

我的建议：写递归前用一句话在图上面标注清楚——这个函数向上层返回什么，全局更新放在哪里。如果一句话说不清，说明设计有问题。

7.4 进栈顺序和访问顺序混了

迭代遍历时，栈里的顺序和访问顺序经常混。中序遍历用栈时，你要先把左链全部压栈，弹出节点时处理节点值，再把右子树压栈。如果把右子树先压栈，节点顺序就变了。这类错误代码能跑起来，但结果错误，而且不容易一眼看出来。

7.5 边界下标算错

重建二叉树（105、106）所有数组越界都源自下标计算错误。排查顺序是：先把inLeft、inRight、inRootIdx、leftLen这些变量的含义写在草稿上，再代入一个验证样例算一遍。我在这个坑上至少跳过两次，后来完成了一道硬性习惯：写这类题必须先在纸上画一遍，再写代码。

7.6 整数溢出

二叉树题里int溢出不常见，但凡是涉及“累加路径和”“前缀和”“负数最大值”的题都要留心。最大路径和里有负数，ans初始值应该是Integer.MIN_VALUE，不能是 0；437 题的前缀和 Map 的 key 用Long。这些细节都属于“测试用例边界很刁钻”的类型。

7.7 全局变量没重置

用成员变量保存答案时，多次测试调用会互相污染。LeetCode 每次提交都会新建一个 Solution 实例，所以成员变量没问题；但如果你在自己的本地测试里复用同一个 Solution 对象，上一轮的状态就会影响下一轮。

我给自己定了一个自查顺序：先查空指针，再查递归出口，再查返回值语义，再查下标/溢出。80% 的错误能在前两步解决，剩下 20% 大多数是设计层面的问题。

8. 这个专题刷完之后的下一步，和我保留的几个小习惯

Hot 100 二叉树部分做到这里，其实已经覆盖了绝大部分中等题的题型。我个人的感受是：二叉树题虽然看着多，但只要能做到“给出一道题，先判断它属于遍历型、验证型、构造型还是最值型”，基本就成功了一半。因为每种类型对应的套路是有限的。

继续往后走，你可以主动挑几道 Hard 题练手，比如二叉树的序列化与反序列化（297）、二叉树中的最大路径和变体（虽然 124 已经在 Hot 100 里）、Morris 遍历实现的 O(1) 空间前中序。这些题的底层思路都是这个专题已经练过的：序列化本质是“先序遍历 + 空节点标记”，Morris 本质是“借用前驱节点的右指针”，并没有跳出这个专题的框架。

我还保留了几个自己觉得很有用的习惯，分享给你。

第一个习惯是画图。任何二叉树题，哪怕是已经会做的，我也会先把测试用例的树画出来。节点结构一旦可视化，递归调用栈的设计就会清楚很多。

第二个习惯是写注释说明返回值语义。我会在递归函数上方用一行注释写明“返回值为……”，而不是等到写完代码再补。这个习惯帮我规避了大量语义混乱的问题。

第三个习惯是小用例先跑。空树、单节点、左右单链这三种极端形态，几乎每道题都值得先跑一遍。很多运行时错误在极端用例下会立刻暴露。

最后一个建议：把做过的题按类型整理成自己的笔记，每题只留一句话的解题核心，比如“验证 BST：区间约束”“层序遍历：队列 + size 快照”“最大路径和：后序贡献值 + 全局答案”。等你刷到后面回头翻笔记，会发现你记住的不再是一道道孤立的题，而是一棵完整的解题树。这才是刷题真正的积累方式。