[LeetCode] Most Frequent Subtree Sum

508. Most Frequent Subtree Sum

Given the root of a binary tree, return the most frequent subtree sum. If there is a tie, return all the values with the highest frequency in any order.

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).

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
unordered_map<int, int> freq;
int helper(TreeNode* node) {
if(!node) return 0;
int res = helper(node->left) + helper(node->right) + node->val;
freq[res]++;
return res;
}
public:
vector<int> findFrequentTreeSum(TreeNode* root) {
helper(root);
vector<int> res;
for(auto& [k, v] : freq) {
if(res.empty()) res.push_back(k);
else if(freq[res[0]] == v) res.push_back(k);
else if(freq[res[0]] > v) continue;
else {
res.clear();
res.push_back(k);
}
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/06/13/PS/LeetCode/most-frequent-subtree-sum/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.