508. Most Frequent Subtree Sum

The description of the problem

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

 

 source ： Power button （LeetCode）
 link ：https://leetcode.cn/problems/most-frequent-subtree-sum

an example

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

The intuition for this problem

the recursive method to add all the substree summarization
use the unordered_map STL to find collect the summary value and its appearance time

The corresponding codes

#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;
// 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 {
    
private:
    unordered_map<int, int> cnt_;
    int max_cnt_;
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
    
        vector<int> res;
        tree_sum(root);
        for (auto it = cnt_.begin(); it != cnt_.end(); ++it) {
    
            if (it->second == max_cnt_) {
    
                res.emplace_back(it->first);
            }
        }
        return res;
    }
    int tree_sum(TreeNode* root) {
    
        if(!root) return 0;
        int sum = root->val + tree_sum(root->left) + tree_sum(root->right);
        ++cnt_[sum];
        max_cnt_ = max(max_cnt_, cnt_[sum]);
        return sum;
    }
};
int main() 
{
    
    Solution s;
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(2);
    root->right = new TreeNode(-3);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);
    root->right->left = new TreeNode(-2);
    root->right->right = new TreeNode(7);
    auto res = s.findFrequentTreeSum(root);
    cout << "res: ";
    for (auto &i : res) {
    
        std::cout << i << " ";
    }

    return 0;
}

The result

$ ./test
res: 13 2 7 6 3 -2 1 %