Short and easy C++ solution 16ms


  • 0
    K
    class Solution {
    public:
        vector<int> findFrequentTreeSum(TreeNode* root) {
            vector<int> v;
            if(root == NULL) return v;
            // [sum->occurences]
            unordered_map<int,int> map;
            // The maximum occurences of the most popular sum
            int max = INT_MIN;
            
            findFrequentTreeSumHelper(root, map, max);
            
            // Iterate over the map and add to the vector the most common sums
            for(auto it : map)
            {
                if(max == it.second) v.push_back(it.first);
            }
            
            return v;
        }
        
        int findFrequentTreeSumHelper(TreeNode* node, unordered_map<int,int>& map, int& max)
        {
            if(node == NULL) return 0;
            // Calculate the current sum of the subtree of this node (including the node itself)
            int currSum = node->val + findFrequentTreeSumHelper(node->left, map, max) + findFrequentTreeSumHelper(node->right, map, max);
            
            // Increase the occurence of the sum in the tree
            map[currSum]++;
            // Update the maximum in case the sum is more frequently shown in the tree
            max = (max < map[currSum] ? map[currSum] : max);
            
            
            return currSum;
        }
    };

Log in to reply
 

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