按照定义求解即可,先计算各个node的节点和,同时保存在hash表中
然后遍历寻找频率最高的节点
ref{:target=”_blank”}
C++ 代码
/**
* 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 {
public:
map<int, int> cnt_; // sum-cnt
vector<int> findFrequentTreeSum(TreeNode* root) {
dfs(root);
int max_cnt = 0;
for(auto& cnt : cnt_) {
max_cnt = max(max_cnt, cnt.second);
}
vector<int> res;
for(auto& cnt : cnt_) {
if(max_cnt == cnt.second) res.push_back(cnt.first);
}
return res;
}
int dfs(TreeNode* root) {
if(!root) return 0;
int val = root->val;
int res = val + dfs(root->left) + dfs(root->right);
cnt_[res]++;
return res;
}
};