Most Frequent Sum
https://app.codesignal.com/interview-practice/task/9i2KvkNRzncy7Bzia
---
The sum of a subtree is the sum of all the node values in that subtree, including its root.
Given a binary tree of integers, find the most frequent sum (or sums) of its subtrees.
Example
- For
t = {
"value": 1,
"left": {
"value": 2,
"left": null,
"right": null
},
"right": {
"value": 3,
"left": null,
"right": null
}
}
the output should bemostFrequentSum(t) = [2, 3, 6].
Since all the sum values in this tree occur only once, return all of them in ascending order.
- For
t = {
"value": -2,
"left": {
"value": -3,
"left": null,
"right": null
},
"right": {
"value": 2,
"left": null,
"right": null
}
}
the output should bemostFrequentSum(t) = [-3].
There are 3 subtree sums for this tree: -2 + (-3) + 2 = -3, -3, and -2. The most frequent sum is -3 since it appears twice.
Input/Output
[execution time limit] 3 seconds (java)
[input] tree.integer t
A tree of integers.
Guaranteed constraints:
0 ≤ tree size ≤ 105,-20000 ≤ node value ≤ 20000.[output] array.integer
- The most frequent subtree sum. If there are several such sums, return them sorted in ascending order.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // | |
| // Binary trees are already defined with this interface: | |
| // class Tree<T> { | |
| // Tree(T x) { | |
| // value = x; | |
| // } | |
| // T value; | |
| // Tree<T> left; | |
| // Tree<T> right; | |
| // } | |
| int[] mostFrequentSum(Tree<Integer> t) { | |
| if (t == null) { | |
| return new int[0]; | |
| } | |
| Map<Integer, Integer> map = new HashMap<Integer, Integer>(); | |
| dfs(t, map); | |
| int max = 0; | |
| List<Integer> ans = new ArrayList<Integer>(); | |
| for (Map.Entry<Integer, Integer> entry: map.entrySet()) { | |
| if (entry.getValue() > max) { | |
| ans = new ArrayList<Integer>(); | |
| ans.add(entry.getKey()); | |
| max = entry.getValue(); | |
| } else if (entry.getValue() == max) { | |
| ans.add(entry.getKey()); | |
| } | |
| } | |
| Collections.sort(ans); | |
| int[] ret = new int[ans.size()]; | |
| for (int i = 0; i < ans.size(); i++) { | |
| ret[i] = ans.get(i); | |
| } | |
| return ret; | |
| } | |
| int dfs(Tree<Integer> node, Map<Integer, Integer> map) { | |
| if (node == null) { | |
| return 0; | |
| } | |
| int left = dfs(node.left, map); | |
| int right = dfs(node.right, map); | |
| int ans = node.value + left + right; | |
| map.put(ans, map.getOrDefault(ans, 0) + 1); | |
| return ans; | |
| } |
