LeetCode 501二叉搜索树中的众数Find Mode in BST——单次中序遍历实现 O(1) 额外空间的解法【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文以 leetcode 题解仓库中的 problems/501.Find-Mode-in-Binary-Search-Tree-en.md 为主体系统讲解含重复值二叉搜索树BST众数查找这一经典问题从最直观的 HashMap 统计思路到利用 BST 中序遍历有序性质实现不使用额外空间递归隐式栈不计的进阶解法并逐行解析 Java 实现。读完本文你将掌握有序遍历 相邻元素比较计数这一可复用于多数与 BST 相关题目的核心技巧。问题描述与题目考点题目给定一棵包含重复节点值的二叉搜索树BST找出其中所有出现次数最多的元素众数。题目对应 LeetCode 501 Find Mode in Binary Search Tree。注意本题对 BST 的定义做了针对重复值的放宽与经典定义不同左子树中所有节点的键值小于等于当前节点键值右子树中所有节点的键值大于等于当前节点键值左右子树本身也必须是二叉搜索树。示例给定 BST[1,null,2,2]其结构为1 \ 2 / 2返回值应为[2]。题目提示若一棵树存在多个众数可以按任意顺序返回它们。Follow Up核心考点能否在不使用任何额外空间的前提下完成题目约定递归产生的隐式栈空间不计入额外空间。这道题的难点并不在统计频率而在 Follow Up 的空间约束如何摆脱 HashMap/数组等辅助结构在一趟遍历内同时完成计数、众数更新与结果收集。思路一HashMap 统计最直观的解法原题解文档给出的第一个思路非常朴素遍历、计数、记录三步走。用一次遍历任意顺序均可访问每个节点借助map键为节点值值为出现次数完成计数遍历结束后扫描 map找出频次等于最大值的所有键。该方案逻辑最简单、对树的形态没有任何要求缺点是空间复杂度为 O(n)需要存储所有不同值及其计数无法满足 Follow Up 的约束。它的价值在于为后续优化提供对照基准。思路二利用 BST 中序遍历有序性实现 O(1) 额外空间原题解文档给出了不借助额外空间的方案其成立完全依赖两条性质BST 的中序遍历结果是一个有序数组。这一性质在本仓库中被反复强调在 thinkings/tree.md 中明确指出二叉搜索树的中序遍历的结果是一个有序数组并以此解释了 problems/98.validate-binary-search-tree.md中序遍历后两两判断是否逆序与 problems/230.kth-smallest-element-in-a-bst.md遍历到第 k 个即返回的解法thinkings/binary-tree-traversal.md 也给出了中序遍历左-根-右的实现要点。由此可见遇到二叉搜索树优先考虑中序遍历是本仓库中序遍历专题反复强调的解题模式。在有序数组中相同的元素必然连续出现。因此中序遍历过程中只需要把当前节点的值与上一个节点的值做比较就能判断同一值的连续段是否还在延续完全不需要 HashMap。于是计数逻辑被压缩为三个变量preNode中序遍历序列中的上一个节点count当前连续相同值的出现次数max目前发现的最大频次。由于题目要求返回所有众数而众数个数事先未知原题解文档特别指出使用ArrayList动态收集结果是一个合适的选择——它既可以随时追加、清空也能在最后方便地转换为int[]返回。Java 代码逐行解析原题解文档给出的 Java 实现如下代码结构完整保留并补充逐行说明/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } */ class Solution { ListInteger list new ArrayList (); // 收集众数结果数量未知所以用动态数组 TreeNode preNode null; // 中序遍历序列中的前驱节点 int max 0, count 0; // 最大频次 与 当前连续值频次 public int[] findMode(TreeNode root) { helper(root); int[] res new int[list.size()]; for (int i0; ires.length; i) { res[i] list.get(i); } return res; } private void helper (TreeNode root) { if (root null) return; helper(root.left); // 中序先左 // 与上一个节点同值 → 连续段延续count if (preNode ! null root.val preNode.val) { count; } else { // 值发生变化 → 开启新的连续段 count 1; } if (count max) { // 出现新的更高频次清空旧结果记录新众数 list.clear(); list.add(root.val); max count; } else if (max count) { // 频次与当前最大值相等追加为并列众数 list.add(root.val); } preNode root; // 移动前驱指针 helper(root.right); // 中序后右 } }关键执行逻辑拆解中序框架helper(root.left) → 处理当前节点 → helper(root.right)即左-根-右。由于 BST 中序遍历得到递增有序序列相同值的节点在遍历时必然相邻出现这是整个算法正确性的前提。连续段计数preNode ! null root.val preNode.val成立说明当前节点与上一个节点同值count自增否则说明进入了新的值段count重置为 1当前节点本身算第一次出现。众数动态维护当count max时说明当前值打破了最高频次纪录此时旧结果已失效需要list.clear()后加入当前值并更新max当count max时说明当前值与历史最高频并列追加到结果列表即可。这一先清空再记录的技巧保证了多众数场景下结果列表始终只包含频次等于max的值。收尾转换findMode在遍历结束后将ArrayListInteger转换为int[]返回满足题目对返回类型的约定。复杂度分析时间复杂度O(n)n 为二叉树节点数。每个节点恰好被中序遍历访问一次每次访问只做常数次比较与列表操作。空间复杂度O(1) 额外空间不计递归隐式栈。全程只使用了list结果集本身不计入辅助空间、preNode、max、count等常量级状态。若不要求返回数组而允许就地输出连list都可省去。与原题解文档一致这里不借助 HashMap 或数组进行计数因此严格满足 Follow Up 的无额外空间约束代价是必须依赖 BST 的结构性质无法直接套用于任意二叉树。从源码结构看该解法的边界与适用前提从上述实现可以推断出几个值得注意的边界空树helper(null)直接返回list为空最终返回长度为 0 的空数组符合题意。单节点树count初始为 1max初始为 0首个节点必然触发count max分支正确返回[root.val]。多众数例如[1,1,2,2]这样的树遍历到第二个 1 时count max 2追加 1遍历到第二个 2 时同样追加 2最终返回[1, 2]顺序无关紧要。适用前提该解法只对中序遍历有序的 BST 成立。若二叉树不满足 BST 性质如乱序的一般二叉树相同值不会连续出现此计数逻辑会失效此时应退回思路一的 HashMap 统计。关联拓展中序遍历在 BST 类题目中的复用本题解法与仓库中其他 BST 题目共享同一思想内核——中序遍历 相邻节点关系problems/98.validate-binary-search-tree.md中序遍历后两两判断是否存在逆序对若有则不是 BSTproblems/230.kth-smallest-element-in-a-bst.md利用中序遍历有序性遍历到第 k 个节点即为第 k 小元素thinkings/binary-tree-traversal.md中序遍历左-根-右的递归与迭代实现thinkings/tree.md系统性阐述 BST 性质——二叉搜索树的中序遍历的结果是一个有序数组并给出遇到二叉搜索树则考虑中序遍历的解题提示。掌握了BST 中序遍历有序 → 相同值连续出现 → 只需比较相邻节点即可完成统计这条链路就能在 501 之外将同样的思路迁移到验证 BST、求第 k 小元素、求相邻节点最小差值等一类题目中。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考