给你一个二叉树的根结点 root
,请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同,返回所有出现次数最多的子树元素和(不限顺序)。
一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和(包括结点本身)。
示例 1:
输入: root = [5,2,-3] 输出: [2,-3,4]
读懂题
举例大一点的树,如这样一颗树:
5
/ \
2 -3
/ \
4 -1
子树和会计算为:
5的子树和: 5 + 2 + 4 + (-1) + (-3) = 7
2的子树和: 2 + 4 + (-1) = 5
-3的子树和:-3
4的子树和: 4
-1的子树和:-1
输出将是所有子树和,因为它们都出现一次,返回 [7, 5, -3, 4, -1]。
class Solution {
public:
unordered_map<int,int> mp;
int maxcount=0;
int dfs(TreeNode *root)
{if(!root){return 0;}int leftSum=dfs(root->left);int rightSum=dfs(root->right);int num = root->val + leftSum + rightSum;mp[num]++;maxcount=max(mp[num],maxcount);return num;
}vector<int> findFrequentTreeSum(TreeNode* root) {vector<int> res;dfs(root);for(auto &[s,c]:mp){if(c==maxcount){res.push_back(s);}}return res;}
};