1. LeetCode 501 题核心知识点解析
作为刷过300+题的过来人，我发现在二叉搜索树（BST）类题目中，501题《二叉搜索树中的众数》是个非常典型的考察点。这道题不仅要求掌握BST的中序遍历特性，还需要灵活运用哈希表和指针操作来统计频率。下面我会从解题思路、代码实现到优化技巧，完整拆解这道高频面试题。
关键提示：BST的中序遍历结果必然是有序数组，这是解决本题的核心突破口
1.1 题目重述与示例分析
给定一个有重复值的二叉搜索树（BST），要求找出其中出现频率最高的元素（众数）。注意：
- 众数可能有多个（出现次数相同）
- 进阶要求：不使用额外空间（递归栈除外）
示例：
输入: [1,null,2,2] 1 \ 2 / 2 输出: [2]这个例子中，2出现了两次，而1只出现一次，因此众数是2。如果是[1,1,2,2]则应该返回[1,2]。
1.2 暴力解法与哈希表统计
最直观的思路是遍历整棵树，用哈希表统计每个值出现的次数：
from collections import defaultdict class Solution: def findMode(self, root): count = defaultdict(int) def traverse(node): if not node: return count[node.val] += 1 traverse(node.left) traverse(node.right) traverse(root) max_count = max(count.values()) if count else 0 return [k for k,v in count.items() if v == max_count]这种方法时间复杂度O(N)，空间复杂度O(N)，虽然能AC但不满足进阶要求。它的优势在于：
- 代码直观易理解
- 适用于任何二叉树（不依赖BST特性）
- 可以处理val为负数的情况
但面试官通常会追问："能否利用BST的特性进行优化？"
2. 中序遍历的妙用
2.1 BST的有序特性
BST的中序遍历结果是一个非递减序列。对于示例树：
中序遍历结果：[1,2,2]我们可以像处理有序数组一样，在遍历时比较当前节点与前驱节点的值：
class Solution: def findMode(self, root): self.prev = None self.current_count = 0 self.max_count = 0 self.result = [] def inorder(node): if not node: return inorder(node.left) # 左 # 处理当前节点 if node.val == self.prev: self.current_count += 1 else: self.current_count = 1 if self.current_count > self.max_count: self.max_count = self.current_count self.result = [node.val] elif self.current_count == self.max_count: self.result.append(node.val) self.prev = node.val inorder(node.right) # 右 inorder(root) return self.result2.2 双指针法的实现细节
这个解法使用类成员变量保存状态：
prev：记录前驱节点值current_count：当前值的连续出现次数max_count：全局最大出现次数result：结果列表
关键操作流程：
- 当
node.val == prev时，current_count递增 - 当值变化时，重置
current_count = 1 - 每次更新
current_count后与max_count比较：- 若更大：清空结果列表，加入当前值
- 若相等：追加当前值
- 若更小：不做处理
时间复杂度O(N)，空间复杂度O(1)（不考虑递归栈）
3. 迭代解法与Morris遍历
3.1 用栈模拟中序遍历
递归解法可能引发栈溢出，改用迭代：
class Solution: def findMode(self, root): stack = [] curr = root prev = None max_count = current_count = 0 result = [] while stack or curr: while curr: stack.append(curr) curr = curr.left curr = stack.pop() if prev == curr.val: current_count += 1 else: current_count = 1 if current_count > max_count: max_count = current_count result = [curr.val] elif current_count == max_count: result.append(curr.val) prev = curr.val curr = curr.right return result3.2 Morris遍历实现O(1)空间
终极优化是使用Morris遍历，避免使用递归栈和显式栈：
class Solution: def findMode(self, root): curr = root prev = None max_count = current_count = 0 result = [] while curr: if not curr.left: self.process_node(curr, prev, result, current_count, max_count) prev = curr curr = curr.right else: predecessor = curr.left while predecessor.right and predecessor.right != curr: predecessor = predecessor.right if not predecessor.right: predecessor.right = curr curr = curr.left else: predecessor.right = None self.process_node(curr, prev, result, current_count, max_count) prev = curr curr = curr.right return result def process_node(self, node, prev, result, current_count, max_count): if node.val == prev: current_count += 1 else: current_count = 1 if current_count > max_count: max_count = current_count result.clear() result.append(node.val) elif current_count == max_count: result.append(node.val)Morris遍历通过修改树结构（临时添加右指针）实现遍历，完成后恢复原状。虽然代码复杂，但在空间限制严格时非常有用。
4. 边界条件与测试案例
4.1 必须考虑的边界情况
- 空树：
root = None→ 返回[] - 所有值唯一：
[1,2,3]→ 返回[1,2,3] - 多个众数：
[1,1,2,2]→ 返回[1,2] - 单节点树：
[1]→ 返回[1] - 负数值：
[-1,-1,-2]→ 返回[-1]
4.2 测试用例设计技巧
建议按以下顺序验证：
def test_findMode(): s = Solution() # 普通情况 root1 = TreeNode(1) root1.right = TreeNode(2) root1.right.left = TreeNode(2) assert s.findMode(root1) == [2] # 多个众数 root2 = TreeNode(1) root2.left = TreeNode(1) root2.right = TreeNode(2) root2.right.left = TreeNode(2) assert sorted(s.findMode(root2)) == [1,2] # 空树 assert s.findMode(None) == [] # 单节点 assert s.findMode(TreeNode(0)) == [0]5. 复杂度分析与对比
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 哈希表统计 | O(N) | O(N) | 任意二叉树，代码简单 |
| 递归中序 | O(N) | O(H)递归栈 | BST标准解法 |
| 迭代中序 | O(N) | O(H)显式栈 | 避免递归栈溢出 |
| Morris遍历 | O(N) | O(1) | 严格空间限制 |
实际面试中建议：
- 先给出哈希表解法（体现基础能力）
- 主动优化到中序遍历解法（展示BST特性理解）
- 如果面试官追问，再讨论Morris遍历
6. 常见错误与调试技巧
6.1 高频错误类型
未重置current_count：当遇到新值时忘记重置计数器
# 错误示例 if node.val == prev: current_count += 1 # 缺少else分支结果更新逻辑错误：
# 错误示例：没有清空结果列表 if current_count >= max_count: # 应该用> result.append(node.val)prev初始化问题：使用
float('-inf')可能不兼容所有测试用例
6.2 Debug实操建议
打印中序遍历序列：
def inorder(node): if not node: return inorder(node.left) print(node.val, end=' ') inorder(node.right)添加调试输出：
print(f"val={node.val}, prev={prev}, count={current_count}, max={max_count}")可视化小树结构：
用缩进表示层级： root \ 2 / 2
7. 举一反三与相似题目
掌握501题后，可以解决以下变种：
BST中前驱后继：利用中序遍历特性
- 285题《BST中的中序后继》
- 510题《BST中的中序前驱II》
频率统计问题：
- 347题《前K个高频元素》
- 451题《根据字符出现频率排序》
BST验证与操作：
- 98题《验证BST》
- 538题《把BST转换为累加树》
核心思维：BST的中序遍历结果是有序数组，许多问题可以转化为数组问题处理
