Task

Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.

Example

Examples 1

1
2
3
4
5
6

Input:

  5
 /  \
2   -3
return [2, -3, 4], since all the values happen only once, return all of them in any order.

Examples 2

1
2
3
4
5
6

Input:

  5
 /  \
2   -5
return [2], since 2 happens twice, however -5 only occur once.

Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.

Solution

  • 使用递归求解每个节点上的sum。由于每个节点都需要维护一个sum值，故将递归函数的返回值设为该sum。这样父节点只需递归调用子节点，就可从递归函数的返回值中计算自己的sum，不需重复计算
  • 维护3个成员变量：
    • 记录每个sum出现频率的字典freqs
    • 记录最终结果的数组ans
    • 记录最大频率的max_freq
  • 每个节点计算完sum后，使字典freqs中对应的频率+1，并将频率与目前的最大频率max_freq比较：
    • 若该sum的频率等于最大频率，则将该sum放进ans数组中
    • 若该sum的频率大于最大频率，则更新最大频率，更新ans数组（清空后放入当前sum）
  • 时间复杂度：每个节点只需计算一次（因为子节点的结果从函数中返回），故O(n)
  • 空间复杂度：取决于递归深度O(h)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

// Runtime: 28 ms, faster than 81.96% of C++ online submissions for Most Frequent Subtree Sum.
// Memory Usage: 25.4 MB, less than 14.95% of C++ online submissions for Most Frequent Subtree Sum.
/**
 * 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:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        get_sum(root);
        return ans;
    }
private:
    int get_sum(TreeNode *root){
        //递归终点，空姐点不增加sum
        if(!root) return 0;
        //递归求解当前节点的sum
        int sum=root->val+get_sum(root->left)+get_sum(root->right);
        //更新频率字典freqs
        int freq=++freqs[sum];
        //若该sum的频率等于最大频率，则将该sum添加进结果数组中
        if(freq==max_freq)
            ans.push_back(sum);
        //若该sum的频率大于最大频率，则更新最大频率和结果数组
        if(freq>max_freq){
            max_freq=freq;
            ans.clear();
            ans.push_back(sum);
        }
        //每个节点返回自己的sum，便于父节点直接计算
        return sum;
    }
    //记录每个sum出现的频率
    unordered_map<int,int> freqs;
    //记录最大频率的sum值
    vector<int> ans;
    //记录最大频率
    int max_freq=-1;
};