508_出现次数最多的子树元素和

发表于 分类于 ， 阅读次数： Waline： 本文字数： 985 阅读时长 ≈ 1 分钟

508. 出现次数最多的子树元素和

给你一个二叉树的根结点 root，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

示例：

输入: root = [5,2,-3]

输出: [2,-3,4]

思路：

DFS + 哈希表：

我们每次判断

1
2
3
unordered_map<int,int> mp;
sum = root->val + leftSum + rightSum;
maxCnt = max(maxCnt, ++mp[sum]);

时间复杂度为：O(n)

空间复杂度为：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maxCnt = 0;
    unordered_map<int,int> mp;
    vector<int> findFrequentTreeSum(TreeNode* root) {
        dfs(root);
        vector<int> res;
        for(auto &[s, c] : mp){
            if(c == maxCnt){
                res.push_back(s);
            }
        }
        return res;
    }
    int dfs(TreeNode *root){
        if(root == nullptr){
            return 0;
        }
        int sum = root->val + dfs(root->left) + dfs(root->right);
        // 更新出现度最大次数
        maxCnt = max(maxCnt, ++mp[sum]);
        return sum;
    }
};