C++ Soultion using Treesum and map


  • 0
    P

    Finding Tree sum gives us subtree sum all nodes in O(n)time. Keep track of the elements and their frequency.

    class Solution {
    public:
        map<int,int >mp;
        TreeNode* transformTree(TreeNode* root){
            if(!root)return NULL;
            root->left = transformTree(root->left);
            root->right = transformTree(root->right);
            int v1 = (root->left)?(root->left->val):0;
            int v2 = (root->right)?(root->right->val):0;
            root->val+=v1+v2;
            mp[root->val]++;
            return root;
        }
        vector<int> findFrequentTreeSum(TreeNode* root) {
            root = transformTree(root);
            int count = 0;
            for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++){
                if(it->second > count)
                    count = it->second;
            }
            vector<int >temp;
            for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++){
                if(it->second == count)
                    temp.push_back(it->first);
            }
            return temp;
        }
    };
    

Log in to reply
 

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