LeetCode 题解工作台
二叉搜索树中的众数
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数 （即，出现频率最高的元素）。 如果树中有不止一个众数，可以按 任意顺序 返回。 假定 BST 满足如下定义： 结点左子树中所含节点的值 小于等于 当前节点的值 结点右子树中所含节点的值 大于等于 当前节点…
4
题型
5
代码语言
3
相关题
当前训练重点
简单 · 二分·树·traversal
答案摘要
class Solution: def findMode(self, root: TreeNode) -> List[int]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1：
输入：root = [1,null,2,2] 输出：[2]
示例 2：
输入：root = [0] 输出：[0]
提示：
- 树中节点的数目在范围
[1, 104]内 -105 <= Node.val <= 105
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
解题思路
方法一
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findMode(self, root: TreeNode) -> List[int]:
def dfs(root):
if root is None:
return
nonlocal mx, prev, ans, cnt
dfs(root.left)
cnt = cnt + 1 if prev == root.val else 1
if cnt > mx:
ans = [root.val]
mx = cnt
elif cnt == mx:
ans.append(root.val)
prev = root.val
dfs(root.right)
prev = None
mx = cnt = 0
ans = []
dfs(root)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Can the candidate demonstrate efficient tree traversal and state tracking simultaneously?
- question_mark
Does the candidate understand how to manage space complexity while maintaining correctness?
- question_mark
How well does the candidate optimize the solution for large input sizes?
常见陷阱
外企场景- error
Not considering the constant space complexity requirement for the final result array.
- error
Forgetting to handle cases with multiple modes or ensuring that all modes are returned in the correct format.
- error
Not accounting for the tree's potentially large size and failing to optimize the space and time complexity accordingly.
进阶变体
外企场景- arrow_right_alt
What if the tree is unbalanced? Does the solution still work efficiently?
- arrow_right_alt
How would the solution change if the problem required identifying the k most frequent elements instead of all modes?
- arrow_right_alt
Can the solution be modified to return the mode with the lowest value if there are multiple modes?