Day18 刷到二叉树 part06这三道题放在一起其实挺有讲究的。530 和 501 都是二叉搜索树BST的题目核心都在啃“中序遍历有序”这个性质236 则是完全不同的路子考的是递归回溯的理解深度。我刷完这一组最大的感受是二叉树的很多题目卡点往往不在“会不会遍历”而在“有没有意识到树的特殊性质能帮你省掉多少无用功”。这篇就把三道题的完整思路、代码实现和踩过的坑一次性说清楚。1. 三道题的共性与整体解题思路1.1 为什么把这三道题放在同一个专题先说一个整体印象。530 求 BST 中任意两节点的最小绝对差501 求 BST 中的众数这两道题如果你不知道 BST 的特性也能做但做出来的代码又丑又慢。一旦你抓住了“BST 中序遍历得到的是一个递增序列”这个点两道题直接从“需要额外数据结构”降级成“一次遍历搞定”。236 看起来画风突变从二叉搜索树换成了普通二叉树还要求最近公共祖先。但这道题其实是对“递归返回值”理解的极致考验。前面的题你递归时可能只是顺手更新一个全局变量而 236 需要你真正想清楚递归函数每一层返回什么上层拿这个返回值做什么。所以这一组放在一起本质上是把“二叉树递归”这个能力从“会用”推向“理解”。前三天的题都是在教你怎么遍历、怎么构造、怎么改结构到这三题就开始要求你理解递归的语义了。1.2 解题前必须刻在脑子里的两个底层认知做这三道题之前有两个底层认知我建议你先建立起来。第一个认知二叉搜索树的中序遍历序列是严格递增的。这意味着什么意味着只要你用中序遍历去访问一棵 BST你就相当于在遍历一个有序数组。凡是要找“相邻差值最小”“出现频率最高”这类问题都可以直接套用有序数组的处理思路。530 和 501 本质上是“有序数组求相邻最小差”和“有序数组求众数”只不过数组是靠遍历现生成的。第二个认知递归函数的返回值是有语义的不是可有可无的装饰。很多初学者写递归返回类型随便填要么直接写成 void 然后靠全局变量要么返回了也不知道上层怎么用。236 这道题会逼你正视这个问题。你不仅要决定“返回什么”还要决定“什么时候返回、什么时候继续往下走”。这两者配合起来就是回溯。这两个认知打通了这三道题基本就解决了一半。2. 530. 二叉搜索树的最小绝对差2.1 题目理解与暴力解法的局限题目给你一棵 BST要求任意两个节点值之差的绝对值的最小值。注意是任意两个节点不只是相邻的两个节点。如果你不知道 BST 的性质第一反应肯定是对每个节点遍历整棵树找最小差也就是 O(n²) 的暴力。这么写在一棵小树上能过但节点数一多就非常难受。而且更关键的是这种暴力解法没有用到题目给 BST 这个条件的任何价值属于典型的“能做但没动脑子”。那有没有更快的解法有。回到那个底层认知BST 中序遍历出来是一个递增数组。在一个递增数组中任意两个元素差的最小值一定出现在相邻两个元素之间。这个可以反证如果 a[i] 和 a[k] 中间隔着其他元素那 a[i] 和 a[i1] 的差一定更小因为 a[i] a[i1] ≤ a[k]。所以问题就变成了中序遍历 BST在遍历过程中比较相邻节点值的差。2.2 双指针遍历写法一次遍历解决既然要比较相邻节点差值最简单的思路就是把中序遍历结果存进一个数组然后扫一遍数组算相邻差。代码很简单class Solution { public int getMinimumDifference(TreeNode root) { ListInteger list new ArrayList(); inorder(root, list); int min Integer.MAX_VALUE; for (int i 1; i list.size(); i) { min Math.min(min, list.get(i) - list.get(i - 1)); } return min; } private void inorder(TreeNode node, ListInteger list) { if (node null) return; inorder(node.left, list); list.add(node.val); inorder(node.right, list); } }这个解法能过但有一个明显的浪费我们其实不需要把整棵树的遍历结果都存下来因为比较相邻节点只需要“当前节点”和“上一个节点”。这就引出双指针写法。用prev指针记录当前节点的前一个节点在遍历过程中实时更新差值不需要额外的存储空间。递归函数本身只负责中序遍历具体的差值计算放在遍历到当前节点时处理class Solution { private TreeNode prev; private int minDiff Integer.MAX_VALUE; public int getMinimumDifference(TreeNode root) { traversal(root); return minDiff; } private void traversal(TreeNode cur) { if (cur null) return; traversal(cur.left); if (prev ! null) { minDiff Math.min(minDiff, cur.val - prev.val); } prev cur; traversal(cur.right); } }这里有个细节为什么cur.val - prev.val一定是正数因为 BST 中序遍历是递增的当前节点一定比上一个节点大。这个性质保证了cur.val - prev.val就是绝对值差不需要再取绝对值。注意prev初始化为 null不要用Integer.MIN_VALUE之类的值去初始化。你可以用哨兵值写但Integer.MIN_VALUE - cur.val可能会溢出而且语义不清晰。用null判断是不是第一个节点干净利落。2.3 易错点递归函数里的变量作用域很多人第一次写这道题会把prev和minDiff定义成局部变量然后发现递归结束后结果不对。原因是递归函数每层调用是一个独立的执行环境prev作为参数传递的话是值传递在函数内部改了也不会影响外层。解决办法有两个要么把prev和minDiff定义成成员变量要么用长度为 1 的数组来模拟“引用传递”。我个人更推荐成员变量理由很直接代码更可读不用写new int[]{...}这种绕来绕去的东西。这也是代码随想录里反复强调的递归需要更新状态时用全局变量或成员变量是最直接的方式。还有一个小坑traversal(cur.left)之后prev才更新为cur这个顺序不能乱。如果先更新prev再遍历左子树等于把“上一个节点”的顺序搞反了结果一定错。这个顺序其实就是中序遍历的顺序先左、再中、再右prev在“中”这一步更新。3. 501. 二叉搜索树中的众数3.1 常规思路的陷阱哈希表计数并不可爱众数问题最无脑的解法是用 HashMap 统计每个值出现的次数然后遍历哈希表找出最大次数对应的所有值。这个解法什么树都能用普通二叉树也行代码写起来也不难class Solution { public int[] findMode(TreeNode root) { MapInteger, Integer countMap new HashMap(); traverse(root, countMap); int maxCount 0; for (int count : countMap.values()) { maxCount Math.max(maxCount, count); } ListInteger result new ArrayList(); for (Map.EntryInteger, Integer entry : countMap.entrySet()) { if (entry.getValue() maxCount) { result.add(entry.getKey()); } } return result.stream().mapToInt(Integer::intValue).toArray(); } private void traverse(TreeNode node, MapInteger, Integer map) { if (node null) return; map.put(node.val, map.getOrDefault(node.val, 0) 1); traverse(node.left, map); traverse(node.right, map); } }这个解法在面试中作为“能跑的方案”是及格的但它有几个问题。第一需要额外的哈希表空间复杂度 O(n)。第二完全没利用 BST 的性质。第三题目明确告诉你这是 BST你却当普通二叉树处理给面试官留下的印象就是“没抓住重点”。那 BST 的众数能不能优化能。还是那条BST 中序遍历是递增序列。递增序列中相同的值一定是连续出现的所以我们可以一边遍历一边统计当前值连续出现的次数。这样就完全不需要哈希表了。3.2 一次遍历找众数维护最大频率与实时更新不用哈希表的核心思想是用count记录当前值连续出现的次数。用maxCount记录到目前为止出现的最大频率。当count maxCount时说明发现了新的众数清空之前的结果集加入当前值。当count maxCount时当前值同样也是众数加入结果集。为什么这套逻辑成立因为中序遍历序列是有序的所有相同的值必然连续出现。只要统计连续段长度就能知道每个值的频率维持一个全局最大频率就能动态筛出所有众数。这里需要特别注意“众数可能不止一个”。如果一棵树里有两个值都出现了 3 次你只返回其中一个就错了。所以结果集要支持动态清空和追加。3.3 核心代码与细节处理class Solution { private ListInteger result new ArrayList(); private int maxCount 0; private int count 0; private TreeNode prev null; public int[] findMode(TreeNode root) { traversal(root); int[] res new int[result.size()]; for (int i 0; i result.size(); i) { res[i] result.get(i); } return res; } private void traversal(TreeNode cur) { if (cur null) return; traversal(cur.left); if (prev null) { count 1; } else if (prev.val cur.val) { count; } else { count 1; } if (count maxCount) { maxCount count; result.clear(); result.add(cur.val); } else if (count maxCount) { result.add(cur.val); } prev cur; traversal(cur.right); } }这个代码有几个值得说道的细节第一个细节prev null时count 1。这是处理遍历到的第一个节点它没有前驱所以当前值连续出现次数只能从 1 开始。如果你把count初始化为 1然后只在prev.val ! cur.val时重置也可以。但用prev null判断更统一不容易漏。第二个细节count maxCount时要clear()结果集。这一步很容易忘。如果不清空当新众数出现时旧的结果还留在里面最终答案就会混入频率不是最大的节点值。第三个细节什么时候该走count maxCount而不是count maxCount当一个值出现了和最大频率一样的次数时它同样是众数。举例树中有值为 1 的节点出现 2 次值为 2 的节点也出现 2 次众数就是 [1, 2]。所以这里必须用if-else if区分两种情况。3.4 边界样例全是同一个值这道题一个隐藏的边界情况是树里所有节点值都相同。比如一棵只有 5 个节点全部为 7 的树遍历过程中count一直递增第一次遇到节点时就count maxCountresult会clear()后加入第一个 7。之后所有节点都是count maxCount吗不是因为maxCount在第一次遇到 7 时已经是 5后续节点的count分别为 2、3、4、5都不会再大于maxCount所以不会重复加入。最终结果就是 [7]这是正确的。如果一开始maxCount初始化为 1当遍历到第一个节点且count为 1 时count maxCount不成立等于会走count maxCount分支直接加入第一个值。这也没问题。关键是逻辑要自洽。4. 236. 二叉树的最近公共祖先4.1 这道题到底在考什么最近公共祖先LCA这道题一上来递归关系比较复杂。先看定义给定一棵二叉树和两个节点 p、q找到这两个节点的最近公共祖先。所谓最近公共祖先就是“离这两个节点最近的、同时是它们祖先的节点”。注意这里有一个隐藏条件p 和 q 一定存在于树中这是题目给定的前提不需要你额外判断。这道题最大的认知难点在于你是在自顶向下的递归过程中完成自底向上的信息收集。前序遍历适合“从上往下传参数”而后序遍历适合“从下往上返回信息”。要找公共祖先你得先知道左右子树里有没有 p 和 q然后才能决定当前节点是不是它们的祖先。这天然就是后序遍历的场景。4.2 递归三要素逐层拆解递归函数的设计分三步。第一步确定终止条件。如果当前节点为空返回 null如果当前节点是 p 或者 q直接返回当前节点。这一步很好理解因为如果当前节点本身就是 p 或 q那它就是能找到的最近祖先候选不需要再往下找了。第二步确定单层递归逻辑。分别去左子树和右子树中找 p 和 q 的返回结果得到left和right。这里有三种情况left和right都不为空说明 p 和 q 分别位于当前节点的左右两侧那当前节点就是最近公共祖先。left为空right不为空说明 p 和 q 都在右子树返回right。right为空left不为空说明 p 和 q 都在左子树返回left。两者都为空返回 null。第三步确定返回值。每一层递归把找到的节点向上返回上层根据左右子树的返回结果做判断。4.3 代码实现与自底向上回溯图解直接看代码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; } if (left ! null) { return left; } return right; } }整个执行过程需要反复推演才能彻底理解。我举个例子一棵最简单的树3 / \ 5 1 / \ 6 2假设 p 6q 2。从根节点 3 开始递归进入左子树 5。在节点 5继续递归左子树 6 就是 p直接返回 6。右子树 2 就是 q直接返回 2。在节点 5left和right都不为空所以 5 是 6 和 2 的最近公共祖先返回 5。回到根节点 3left 5。右子树 1 递归完后right为 null1 的子树里没有 p 和 q。此时在根节点 3left非空、right为空根据逻辑返回left即 5。最终答案就是 5。再想一种情况p 5q 2。从根节点 3 递归左子树节点 5 就是 p直接返回 5。注意这里不会继续往下递归左子树 6 和右子树 2。根节点 3 的left 5right在右子树 1 里找为 null。返回left也就是 5。这里很多人会卡住“那 5 是 2 的祖先吗2 在 5 的子树里所以 5 确实是 2 的祖先同时 5 又是 p 本身。最近公共祖先当然是 5。”这个思路完全正确。4.4 常见误区为什么不能自顶向下找还有人会想我能不能写一个函数判断某棵子树是否包含 p 和 q然后自顶向下找比如从根节点开始如果左子树同时包含 p 和 q就进入左子树找如果右子树同时包含 p 和 q就进入右子树找否则根节点就是答案。这个解法逻辑上没错时间复杂度却很尴尬。判断“是否包含”本身需要 O(n) 的遍历而自顶向下找每层都要判断一次最坏情况下会退化到 O(n²)性能非常差。236 这道题的递归解法之所以优雅是因为它只遍历一遍整棵树在递归回溯过程中就已经把答案确定下来了。4.5 延伸思考如果 p 或 q 不存在怎么办题目保证了 p 和 q 都在树中所以上面的代码没有任何“没找到”的兜底逻辑。但如果你改造成“p 或 q 不存在”的场景这个递归写法就会出问题。比如 p 存在、q 不存在left和right中会有一个返回值最终你会把那个返回值当成 LCA而它实际上是“找到的 p 的那条路径上的父节点”并不是真正的 LCA。要做这个扩展标准的做法是先遍历一次确认两个节点都存在再调用 LCA 函数或者递归返回一个特殊状态同时携带“是否找到 p”“是否找到 q”“当前 LCA 候选”三个信息。这在实战里是另一个题目了不需要死磕但知道这个边界对理解递归返回值语义有帮助。5. 常见问题与排查技巧实录我刷这三道题的过程中以及帮朋友 review 的时候遇到过几个反复出现的典型问题统一整理在这里按题归类方便你对照排查。5.1 530 篇为什么返回 Integer.MAX_VALUE不少人递归写完后发现结果一直是Integer.MAX_VALUE排查半天发现是prev从未被更新。最常见的错误是在traversal(cur.left)之前就prev cur导致每个节点把“自己”当成了“上一个节点”cur.val - prev.val恒为 0最终返回 0。这是一个语义混淆的典型案例把中序遍历的顺序和赋值顺序搞混了。另一个问题是用Math.abs(cur.val - prev.val)去求绝对值。前面说过 BST 的中序序列递增不需要取绝对值。如果你发现自己必须要取绝对值才能保证结果正确那大概率是你的遍历顺序写错了不是“要不要取绝对值”的问题。5.2 501 篇结果集没有清空导致的幻觉众数我最开始写 501 时踩过一个很隐蔽的坑结果集声明在成员变量位置一次测试用例跑通之后第二次跑同一个函数时结果集还带着上一次的数据。如果你的解法不是每调用一次就重置成员变量而是复用同一个对象就会出现“第一棵树众数是 [1]第二棵树的众数却是 [1, 2]”这种诡异结果。排查方法是在findMode方法开头主动清空一次result、重置maxCount和count。LeetCode 的判题系统每次调用会新建一个 Solution 对象所以这个坑在本地跑多个测试用例时才会暴露在线判题不会出错。还有一个细节result.clear()的位置。如果你是在count maxCount之后清空没问题但如果你想写得更严谨可以在进入findMode时就先result.clear()。两种做法效果一样。5.3 236 篇返回值的语义混淆导致死循环236 最常见的错误是递归左子树和右子树之后不知道该怎么处理返回值于是改成“如果左子树返回不为空就返回左子树否则返回右子树”就这行代码很多初学者会疑惑万一 left 返回右子树里找到的节点怎么办其实正确的语义是在每一层递归里你拿到的left和right代表“p 或 q 在这棵子树中的查找结果”。如果两边都有结果当前节点就是答案如果只有一边有结果说明两个节点都在那一边返回那一边的结果即可。这个逻辑和“整棵树的答案是什么”不是一回事但上层会用同样的逻辑继续收敛。只要你递归函数体里写对了返回值就会一路向上传导。调试递归问题时我推荐一个土办法在递归函数入口和出口打日志打印当前节点、left 返回值和 right 返回值。看到一个递归过程中每个节点的返回结果理解起来比空想快得多。刷题时用 debug 模式跑一遍小树胜过反复看十遍题解。6. 实操心得这三道题让我想明白的两件事三道题刷完我自己最深的体会不是记住了某个模板而是对两件事有了新的判断。第一件事BST 的题看到就要条件反射去问自己“能不能用中序遍历”。中序遍历在 BST 上的价值相当于“排序”在数组上的价值——它把复杂的树结构压平成一维的、有顺序的信息流。530 和 501 这两个问题一旦转化成一维递增序列上的问题难度立刻下降一个档。后面你还会遇到很多 BST 的题比如验证二叉搜索树、求第 K 小的元素本质都是这个套路。第二件事递归函数的返回值不是一个可有可无的东西它是函数和调用者之间的契约。236 这道题如果不用返回值只靠外部变量记录状态实现起来会非常别扭。弄清楚“你希望每一层递归告诉上层什么信息”很多时候比硬背模板更能帮你写出正确的递归函数。这一点在后续的二叉树路径问题、动态规划树形 DP 里会反复用到。最后再分享一个小技巧这三道题全部适合用“最小用例法”验证。每写完一个递归函数别急着提交先画一棵只有三五个节点的树手推一遍递归过程。很多时候逻辑错误在最小用例上就会暴露避免你反复提交试错。这个习惯我沿用到现在刷任何树的题目都先跑最小用例效率提升非常明显。