Short and easy C++ solution 16ms

  • 0
    class Solution {
        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
            // 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.