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

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12 
13     int dfs(TreeNode *root)
14     {
15         if (NULL == root)
16         {
17             return 0;
18         }
19 
20         // 计算左右
21         int left = dfs(root->left);
22         int right = dfs(root->right);
23 
24         // 该节点值
25         int sum = root->val + left + right;
26 
27         // 添加到map当中
28         Map[sum]++;
29 
30         return sum;
31     }
32 
33     vector<int> findFrequentTreeSum(TreeNode* root) 
34     {
35         if (NULL == root)
36         {
37             return {};
38         }
39 
40         dfs(root);
41 
42         vector<int> res;
43         int max_count = 0;
44 
45         // 遍历map
46         for (auto c: Map)
47         {
48             if (c.second == max_count)
49             {
50                 res.push_back(c.first);
51             }
52             else if (c.second > max_count)
53             {
54                 res.clear();
55                 res.push_back(c.first);
56                 max_count = c.second;
57             }
58         }
59 
60         return res;
61     }
62     private:
63         map<int, int> Map; // 第一个为当前值, 第二个为频率值
64 };