LC 501. 二叉搜索树中的众数，在计数解法的基础上，利用二叉搜索树中序遍历有序的特性优化空间复杂度。
501. 二叉搜索树中的众数#
https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树
Map计数版本#
看到这类找众数的题目，大脑里蹦出的第一个思路就是直接使用map计数，针对最后计数等于最大计数的元素，收集到一个答案数组即可。
由于这个题目求的可能有多个众数，也无法用「摩尔投票」优化。
思路非常直给，下面展示这部分代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
public static class MapCntSolution {
// 维护每个元素对应的出现次数
Map<Integer, Integer> val2Cnt;
// 维护最多的次数
int maxCnt;
public int[] findMode(TreeNode root) {
val2Cnt = new HashMap<>();
maxCnt = 0;
dfs(root);
List<Integer> majorityList = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : val2Cnt.entrySet()) {
if (entry.getValue() == maxCnt) {
majorityList.add(entry.getKey());
}
}
int[] ans = new int[majorityList.size()];
int i = 0;
for (int majority : majorityList) {
ans[i++] = majority;
}
return ans;
}
private void dfs(TreeNode node) {
if (node == null) {
return;
}
int val = node.val;
int newCnt = val2Cnt.getOrDefault(val, 0) + 1;
maxCnt = Math.max(maxCnt, newCnt);
val2Cnt.put(val, newCnt);
dfs(node.left);
dfs(node.right);
}
}
|
复杂度分析#
需要完整遍历入参的BST，时间复杂度为O(n)。
使用额外的Map维护计数，空间复杂度O(n)。
BST中序遍历版本#
BST与普通二叉树的最大区别就是：BST中元素是有序的。
我们使用中序遍历，即可有序遍历到每个节点。
当序列有序时，我们就可以逐个段维护对应的计数，同时到下一个段时，可以及时更新最大计数。
这样可以优化掉上个版本中的map，省掉了额外的空间开销。
具体的步骤参见下方代码中的注释：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
public static class InOrderBSTSolution {
// 利用BST中序遍历有序的特性，进行有序遍历
// 维护每个段的元素值，segmentVal
int segmentVal;
// 维护每个段的元素出现次数，cnt
int cnt;
// 维护所有端元素的最大出现次数，maxCnt
int maxCnt;
// 使用一个列表维护答案，当最大出现次数更新时，重置列表
List<Integer> ans;
public int[] findMode(TreeNode root) {
segmentVal = root.val;
cnt = 0;
maxCnt = 0;
ans = new LinkedList<>();
inOrderDFS(root);
int[] ansArr = new int[ans.size()];
for (int i = 0; i < ans.size(); i++) {
ansArr[i] = ans.get(i);
}
return ansArr;
}
// 中序遍历，中间每个节点真实的判断与处理一个有序的数组元素一样
private void inOrderDFS(TreeNode node) {
if (node == null) {
return;
}
inOrderDFS(node.left);
handlePerNode(node);
inOrderDFS(node.right);
}
// 有序遍历时，处理每个元素
private void handlePerNode(TreeNode node) {
int nodeVal = node.val;
if (nodeVal == segmentVal) {
// 连续的段，更新计数
cnt++;
} else {
// 更新为一个新的连续的段
segmentVal = nodeVal;
cnt = 1;
}
// 更新出现最多的元素
if (cnt == maxCnt) {
ans.add(nodeVal);
}
// 重置最大计数
if (cnt > maxCnt) {
maxCnt = cnt;
ans.clear();
ans.add(nodeVal);
}
}
}
|
复杂度分析#
依然需要完整遍历入参的BST，时间复杂度为O(n)。
利用了BST中序遍历有序的特性，无需额外维护计数map，空间复杂度O(1)。
很多时候算法题会给出一些题干、设定，其中会隐含一些关键条件，本题中的BST有序就是关键条件。
往往利用好这些关键条件，就能提升算法性能。
这种思路同样适用于工作中的系统设计，一般业务场景、团队诉求会有一定的倾向性，将业务倾向性与技术方案结合，往往就是最合适的方案。