[c++] Easy to understand. Runtime beats 97.41% of cpp submissions


  • 0
    M

    The idea is to dfs the tree and RECORD each node's subtree_sum and frequent to a map, then return their subtree_sum to finish the recusion.

    int subtreeSum(TreeNode* root,map<int,int>&cnt){
            if(!root)
                return 0;
            if(!root->left&&!root->right){
                cnt[root->val]++;
                return root->val;
            }
            int lsum = subtreeSum(root->left,cnt);
            int rsum = subtreeSum(root->right,cnt);
            cnt[root->val+lsum+rsum]++;
            return root->val+lsum+rsum;
        }
        vector<int> findFrequentTreeSum(TreeNode* root) {
            map<int,int>cnt;
            subtreeSum(root,cnt);
            int maxcnt = 0;
            vector<int>rs;
            for(auto it=cnt.begin();it!=cnt.end();it++){
                if(it->second>maxcnt){
                    maxcnt=it->second;
                    rs.clear();
                    rs.emplace_back(it->first);
                }
                else if(it->second==maxcnt){
                    rs.emplace_back(it->first);
                }
            }
            return rs;
        }
    

Log in to reply
 

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