給你一個二叉樹的根結點?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;}
};