MostFrequentSubtreeSum [source code]
public class MostFrequentSubtreeSum {
static
/******************************************************************************/
public class Solution {
public int[] findFrequentTreeSum(TreeNode root) {
Map<Integer, Integer> map = new HashMap<>();
dfs(root, map);
List<Integer> ls = new ArrayList<>();
int maxCount = -1;
for (Integer key : map.keySet()) {
Integer count = map.get(key);
if (count > maxCount) {
maxCount = count;
ls.clear();
ls.add(key);
} else if (count == maxCount) {
ls.add(key);
}
}
// return ls.stream().mapToInt(i -> i).toArray();
int[] res = new int[ls.size()];
for (int i = 0; i < res.length; i++)
res[i] = ls.get(i);
return res;
}
public int dfs(TreeNode root, Map<Integer, Integer> map) {
if (root == null)
return 0;
int left = dfs(root.left, map);
int right = dfs(root.right, map);
int sum = root.val + left + right;
Integer count = map.get(sum);
if (count == null) {
map.put(sum, 1);
} else {
map.put(sum, count + 1);
}
return sum;
}
}
/******************************************************************************/
public static void main(String[] args) {
MostFrequentSubtreeSum.Solution tester = new MostFrequentSubtreeSum.Solution();
}
}
大概看了一眼, 题目好像不难, 明天白天再做了;
题目本身不难, 直接做就行了, 最后一个过程就是一个当给了你所有的counts之后, 找到counts最多的过程, 这个也很简单; 最后的速度是95ms (10%), 比较慢, 不知道为什么;
return ls.stream().mapToInt(i -> i).toArray();
这个是SO上面搜到的一个JAVA8的解决办法for List
知道为什么这么慢了, 就是这个JAVA8的stream的原因, 把这个改成手动做之后, 速度立刻就上去了: 17(77).
这个是discussion上面一个最优解:
public class Solution {
Map<Integer, Integer> sumToCount;
int maxCount;
public int[] findFrequentTreeSum(TreeNode root) {
maxCount = 0;
sumToCount = new HashMap<Integer, Integer>();
postOrder(root);
List<Integer> res = new ArrayList<>();
for (int key : sumToCount.keySet()) {
if (sumToCount.get(key) == maxCount) {
res.add(key);
}
}
int[] result = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
result[i] = res.get(i);
}
return result;
}
private int postOrder(TreeNode root) {
if (root == null) return 0;
int left = postOrder(root.left);
int right = postOrder(root.right);
int sum = left + right + root.val;
int count = sumToCount.getOrDefault(sum, 0) + 1;
sumToCount.put(sum, count);
maxCount = Math.max(maxCount, count);
return sum;
}
}
思路是类似的, 注意他这里的getOrDefault的使用; 以及他在DFS的过程当中就维护这个maxCount, 这样pass2的时候处理就更方便一些, 直接就知道你想要找的目标是什么;
discussion上面提到一个优化, 就是不要DFS之后专门单独一个pass来过Map这个过程是可以省略的. 我考虑了一下, 写了这个代码:
public class Solution {
List<Integer> ls = new ArrayList<>();
int maxCount = -1;
public int[] findFrequentTreeSum(TreeNode root) {
Map<Integer, Integer> map = new HashMap<>();
dfs(root, map);
int[] res = new int[ls.size()];
for (int i = 0; i < res.length; i++)
res[i] = ls.get(i);
return res;
}
public int dfs(TreeNode root, Map<Integer, Integer> map) {
if (root == null)
return 0;
int left = dfs(root.left, map);
int right = dfs(root.right, map);
int sum = root.val + left + right;
int count = map.getOrDefault(sum, 0);
count++;
map.put(sum, count);
if (count > maxCount) {
ls.clear();
ls.add(sum);
maxCount = count;
} else if (count == maxCount) {
ls.add(sum);
}
return sum;
}
}
最后的速度是12(99), 可以看到, 加速非常明显, 这个优化一点也不trivial. 而且根据那个人的说法, 这个其实是真实的面试的时候被问到的Follow-Up;
当然提这个优化的人自己写的代码倒是很丑;
这个是另外一个版本, 省掉了一个list的空间:
public class Solution {
int maxFreq = 0;
int count = 0;
public int[] findFrequentTreeSum(TreeNode root) {
Map<Integer, Integer> map = new HashMap<>();
traverse(root, map);
int[] res = new int[count];
int i = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() == maxFreq) {
res[i++] = entry.getKey();
}
}
return res;
}
private int traverse(TreeNode root, Map<Integer, Integer> map) {
if (root == null) {
return 0;
}
int left = traverse(root.left, map);
int right = traverse(root.right, map);
int sum = left + right + root.val;
map.put(sum, map.getOrDefault(sum, 0) + 1);
if (map.get(sum) > maxFreq) {
maxFreq = map.get(sum);
count = 1;
} else if (map.get(sum) == maxFreq) {
count++;
}
return sum;
}
}
Problem Description
Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.
Examples 1
Input:
5
/ \
2 -3
return [2, -3, 4], since all the values happen only once, return all of them in any order.
Examples 2
Input:
5
/ \
2 -5
return [2], since 2 happens twice, however -5 only occur once.
Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.
Difficulty:Medium
Total Accepted:16.4K
Total Submissions:31.4K
Contributor: Cyber233
Companies
amazon
Related Topics
tree hash table
Similar Questions
Subtree of Another Tree