题目描述

给定一棵树的树根，统计出现频率最高的“子树和”。一个结点的“子树和”定义为以该结点给根结点的子树所有结点的和（包括该结点本身）。所以频率最高“子树和”是哪些？如果出现多个，以任何顺序返回所有出现频率最高的值。

样例

输入:

  5
 /  \
2   -3
输出 [2, -3, 4]，因为所有的值都仅出现了一次，以任何顺序返回即可。

Input:

  5
 /  \
2   -5
输出 [2]，因为值 2 出现了两次，然后值 -5 仅出现了一次。

注意

• 可以假设任意“子树和”在 32 位有符号整数范围内。

算法

(DFS) $O(n)$

1. 通过 DFS 累计每个结点的子树和，并将该和用 unordered_map 进行频率统计。
2. 具体地，遍历到当前结点时，定义 sum 代表当前结点的子树和，然后递归左子树，递归右子树。sum 等于该结点本身的值，加上递归左子树返回的值，再加上递归右子树返回的值。
3. 将 sum 加入 unordered_map 中，然后返回 sum 作为本次递归的返回值。

时间复杂度

• 每个结点仅遍历一次，且 unordered_map 的单次操作复杂度为 $O(1)$，故总时间复杂度为 $O(n)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    unordered_map<int, int> freq;

    int dfs(TreeNode* r) {
        if (r == NULL)
            return 0;

        int sum = r -> val;
        sum += dfs(r -> left);
        sum += dfs(r -> right);
        freq[sum]++;

        return sum;
    }
    vector<int> findFrequentTreeSum(TreeNode* root) {
        dfs(root);
        vector<int> ans;
        int ans_count = 0;
        for (auto f : freq) {
            if (f.second > ans_count) {
                ans_count = f.second;
                ans.clear();
                ans.push_back(f.first);
            }
            else if (f.second == ans_count)
                ans.push_back(f.first);
        }

        return ans;
    }
};