Solution for "Most Frequent Subtree Sum"


  • 0
    S
    /**
     * 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:
        int traverseSum(TreeNode* root, vector<int> &sum) {
            // Exit condition
            if (root == NULL) {
                return 0;
            }
            
            int thisSum = root->val;
    
            thisSum += traverseSum(root->left, sum);
            thisSum += traverseSum(root->right, sum);
    
            sum.push_back(thisSum);            
            
            return thisSum;
        }
        
        vector<int> findFrequentTreeSum(TreeNode* root) {
            // inorder traverse and sum
            vector<int> sum;
            traverseSum(root, sum);
            
            // Build a map with count
            map<int, int> sumCount;
            for (size_t i = 0; i < sum.size(); i++) {
                if (sumCount.find(sum[i]) == sumCount.end()) {
                    sumCount[sum[i]] = 1;
                }
                else {
                    sumCount[sum[i]] += 1;
                }
            }
            
            // Build a set of the result
            int highestCount = 0;
            set<int> result;
            for (auto& it : sumCount) {
                if (it.second > highestCount) {
                    result.clear();
                    highestCount = it.second;
                    result.insert(it.first);
                }
                else if (it.second == highestCount) {
                    result.insert(it.first);
                }
            }
            
            // fill result
            sum.clear();
            for (auto it : result) {
                sum.push_back(it);
            }
            
            return sum;
            
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.