13 ms (93.61%) C++ solution using unordered_map


  • 0
    B

    Steps:

    • Convert the TreeNodes values to root->val + root->leftSubTree->value + root->rightSubTree->value (in bottom up fashion ofcourse).
    • While converting increment the value of computed root->val into hashmap (unordered_map).
    • Iterate the hashmap to find what is the max number of occurrences.
    • Iterate the hashmap again to store the values of all the values occurring max number of times in result vector.
    /**
     * 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:
        vector<int> findFrequentTreeSum(TreeNode* root) {
            std::vector<int> results;
            int max = 0;
            
            ConvertTree(root);
            
            for(std::pair<int, int> pr : mp) {
                if(max < pr.second)
                    max = pr.second;
            }
            
            for(std::pair<int, int> pr : mp) {
                if(pr.second == max)
                    results.push_back(pr.first);
            }
            
            return results;
        }
    private:
        int ConvertTree(TreeNode* root) {
            if(!root)
              return 0;
            int l = ConvertTree(root->left), r = ConvertTree(root->right);
            root->val = root->val + l + r;
            mp[root->val]++;
            return root->val;
        }
        
        std::unordered_map<int, int> mp;
    };
    

Log in to reply
 

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