Version I - hash map + traversal
in this way, there's no difference between each traversal.
public class Solution {
private int maxOccur;
public int[] findMode(TreeNode root) {
Map<Integer, Integer> map = new HashMap<>();
List<Integer> list = new ArrayList<>();
inOrderTraversal(root, map);
for (int key : map.keySet()) {
if (map.get(key) == maxOccur) {
list.add(key);
}
}
int[] result = new int[list.size()];
for (int i = 0; i < list.size(); ++i) result[i] = list.get(i);
return result;
}
private void inOrderTraversal(TreeNode node, Map<Integer, Integer> map) {
//exit
if (node == null) return;
map.put(node.val, map.getOrDefault(node.val, 0) + 1);
maxOccur = Math.max(maxOccur, map.get(node.val));
inOrderTraversal(node.left, map);
inOrderTraversal(node.right, map);
}
}
Version II - what makes BST unique? - in order traversal
do inorder traversal
since the traversal should be an non-descending order (or equal), then, check the value with previous node, if equal, then count++, else reset count
public class Solution {
private TreeNode prevNode;
private int count = 1;
private int max;
public int[] findMode(TreeNode root) {
List<Integer> list = new ArrayList<>();
inOrderTraversal(root, list);
int[] result = new int[list.size()];
for (int i = 0; i < result.length; ++i) result[i] = list.get(i);
return result;
}
private void inOrderTraversal(TreeNode node, List<Integer> list) {
if (node == null) return;
inOrderTraversal(node.left, list);
//compare with prev
if (prevNode != null) {
if (prevNode.val == node.val) {
count++;
} else {
count = 1;
}
}
if (count > max) {
max = count;
list.clear();
list.add(node.val);
} else if (count == max) {
list.add(node.val);
}
prevNode = node;
inOrderTraversal(node.right, list);
}
}