508

508. Most Frequent Subtree Sum (Medium)

Given the root of a binary tree, return the most frequent subtree sum. If there is a tie, return all the values with the highest frequency in any order.

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).

 

Example 1:

Input: root = [5,2,-3]
Output: [2,-3,4]

Example 2:

Input: root = [5,2,-5]
Output: [2]

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -105 <= Node.val <= 105

Companies:
Amazon, Apple

Related Topics:
Hash Table, Tree, Depth-First Search, Binary Tree

Similar Questions:

• Subtree of Another Tree (Easy)
• Count Nodes Equal to Sum of Descendants (Medium)

Solution 1. DFS

// OJ: https://leetcode.com/problems/most-frequent-subtree-sum/
// Author: github.com/lzl124631x
// Time: O(logN)
// Space: O(N)
class Solution {
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        vector<int> ans;
        int maxFreq = 0;
        unordered_map<int, int> m;
        function<int(TreeNode*)> dfs = [&](TreeNode *root) {
            if (!root) return 0;
            int left = dfs(root->left), right = dfs(root->right), sum = left + right + root->val, f = ++m[sum];
            if (f > maxFreq) maxFreq = f, ans = {sum};
            else if (f == maxFreq) ans.push_back(sum);
            return sum;
        };
        dfs(root);
        return ans;
    }
};