Reference: LeetCode
Difficulty: Easy
Problem
Given a binary search tree (BST) with duplicates, find all the
mode(s)
(the most frequently occurred element) in the given BST.
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys
less than or equal to
the node’s key. - The right subtree of a node contains only nodes with keys
greater than or equal to
the node’s key. - Both the left and right subtrees must also be binary search trees.
Note: If a tree has more than one mode, you can return them in any order.
Example:
1 | Given BST: [1,null,2,2] |
Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).
Analysis
Methods:
Hash Map
- In the inorder traversal, we do the counting work and use a hash map to store the values. In the meanwhile, we calculate the
maxCount
. - Iterate the map and add those keys that satisfy the requirement.
- Convert
List<Integer>
toint[]
in a for-loop.Time: $O(N)$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
44private int maxCount = Integer.MIN_VALUE;
public int[] findMode(TreeNode root) {
if (root == null) {
return new int[] {};
}
Map<Integer, Integer> map = new HashMap<>();
inorder(root, map);
// count
List<Integer> resultList = new ArrayList<>();
for (int key : map.keySet()) {
if (map.get(key) == maxCount) {
resultList.add(key);
}
}
// result - convert from List<Integer> to int[] is very annoying, but it is the only to do so.
int[] result = new int[resultList.size()];
for (int i = 0; i < result.length; ++i) {
result[i] = resultList.get(i);
}
return result;
}
private void inorder(TreeNode root, Map<Integer, Integer> map) {
if (root == null) {
return;
}
inorder(root.left, map);
int count;
if (map.containsKey(root.val)) {
count = map.get(root.val) + 1;
map.put(root.val, count);
} else {
count = 1;
map.put(root.val, count);
}
maxCount = Math.max(maxCount, count);
inorder(root.right, map);
}
Space: $O(N)$
- In the inorder traversal, we do the counting work and use a hash map to store the values. In the meanwhile, we calculate the
Get Max First
- In the first traversal, calculate the
maxCount
, later we can add those integers to the list directly in the second traversal.Time: $O(N)$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
58private Integer preVal = null;
private int count = 0;
private int maxCount = Integer.MIN_VALUE;
public int[] findMode(TreeNode root) {
if (root == null) {
return new int[] {};
}
List<Integer> result = new ArrayList<>();
preVal = null; getMax(root);
preVal = null; getResult(root, result);
// convert to int[]
int[] ret = new int[result.size()];
for (int i = 0; i < ret.length; ++i) {
ret[i] = result.get(i);
}
return ret;
}
private void getMax(TreeNode root) {
if (root == null) {
return;
}
getMax(root.left);
if (preVal != null && preVal == root.val) { // same
count += 1;
maxCount = Math.max(maxCount, count);
} else { // not same
count = 1;
preVal = root.val;
maxCount = Math.max(maxCount, count);
}
getMax(root.right);
}
private void getResult(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
getResult(root.left, result);
if (preVal != null && preVal == root.val) { // same
count += 1;
} else { // not same
count = 1;
preVal = root.val;
}
if (count == maxCount) {
result.add(root.val);
}
getResult(root.right, result);
}
Space: $O(1)$
- In the first traversal, calculate the