Description
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.
For example:
Given BST [1,null,2,2],
tree
return [2].
Note: If a tree has more than one mode, you can return them in any order.
Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).
Solution
DFS using HashMap, time O(n), space O(n)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int[] findMode(TreeNode root) {
Map<Integer, Integer> valToCount = new HashMap<>();
int maxCount = findModeHelper(root, valToCount, 0);
List<Integer> modeList = new LinkedList<>();
for (int val : valToCount.keySet()) {
if (valToCount.get(val) == maxCount) {
modeList.add(val);
}
}
int[] modes = new int[modeList.size()];
for (int i = 0; i < modes.length; ++i) {
modes[i] = modeList.get(i);
}
return modes;
}
public int findModeHelper(TreeNode root, Map<Integer, Integer> map, int max) {
if (root == null) {
return max;
}
map.put(root.val, map.getOrDefault(root.val, 0) + 1);
max = Math.max(max, map.get(root.val));
return Math.max(findModeHelper(root.left, map, max)
, findModeHelper(root.right, map, max));
}
}
DFS, time O(n), space O(1)
對(duì)于BST來(lái)說(shuō)，中序遍歷的結(jié)果是遞增的。所以此題目轉(zhuǎn)換成求一個(gè)遞增數(shù)組中出現(xiàn)次數(shù)最多的數(shù)字。
可以用Morris中序遍歷，第一遍遍歷保存maxCount和modeCount褂始，第二遍遍歷再填充返回值。懶得寫了。域那。（其實(shí)不會(huì)寫哈哈）
