Python easy understand solution


  • 15

    I have used a hash-map ctr to count the sum occurrence.

    I have wrote a sub function countSubtreeSum to travel through a tree and return the sum of the tree.

    In countSubtreeSum, I will travel through the left node and the right node, calculate the sum of the tree, increment the counter ctr, and return the sum.

      def findFrequentTreeSum(self, root):
            if root == None: return []
    
            def getSum(node):
                if node == None: return 0
                s = node.val + getSum(node.left) + getSum(node.right)
                c[s] += 1
                return s
    
            c = collections.Counter()
            getSum(root)
            frequent = max(c.values())
            return [s for s in c.keys() if c[s] == frequent]
    

    Please upvote if it makes sense.

    Update: I have changed a little to make the variable name shorter.


  • 2
    D

    @lee215
    I had the exact same concept.

       def findFrequentTreeSum(self, root):
            if not root: return []
            c = Counter()
            
            def getSum(node):
                if not node: return 0
                s = node.val + getSum(node.left) + getSum(node.right)
                c[s] += 1
                return s
                
            getSum(root)
            m = max(c.values())
            return [s for s in c.keys() if c[s] == m]
    

    By the way you have a typo in your solution. countSubtreeSum in your helper function should be countTreeSum.


  • 0
    S

    C++ version

    #include <unordered_map>
    class Solution {
        std::unordered_map<int, int> freqMap;
    public:
        vector<int> findFrequentTreeSum(TreeNode* root) {
            std::vector<int> r;
            if (root == nullptr){
                return r;
            }
            sum(root);
            int maxFreq = -1;
            for (const auto& pair: freqMap){
                if (pair.second > maxFreq)
                    maxFreq = pair.second;
            }
            for (const auto& pair: freqMap){
                if (pair.second == maxFreq)
                    r.push_back(pair.first);
            }
            return r;
            
        }
        
        int sum(TreeNode* root){
            auto s = root->val
                + (root->left == nullptr? 0 : sum(root->left)) 
                + (root->right == nullptr? 0: sum(root->right));
            freqMap[s]++;
            return s;
        }
    };

  • 0
    P

    Same idea, couple of variations:

    • filter instead of list comprehension based filter. (Just for fun)
    • defaultdict instead of Counter. ( defaultdict performs better than Counter )
        def findFrequentTreeSum(self, root):
            if root is None: return []
            freq = collections.defaultdict(int)
    
            def dfs(root):
                if root is None: return 0
                s = dfs(root.left) + dfs(root.right) + root.val
                freq[s] += 1
                return s
    
            dfs(root)
            mx_freq = max(freq.values())
            return filter(lambda s: freq[s] == mx_freq, freq.keys())
    

Log in to reply
 

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