Day104 | 灵神 | 二叉树 出现次数最多的子树元素和

508.出现次数最多的子树元素和

508. 出现次数最多的子树元素和 - 力扣（LeetCode）

思路：

思路就是遍历一遍二叉树然后用map给它的频率都记录下来，再对频率排序，把最大的输出到一个vector里面返回就是了

注意：C++的map不能直接对sort使用lambda实现对value的排序，需要先把map转化为vector<pair>才可以

完整代码：

class Solution {
public:
    map<int,int> q;
    int maxCnt=0;
    //记录频率
    int tra(TreeNode *t)
    {
        if(t==nullptr)
            return 0;
        int sum=tra(t->left)+tra(t->right)+t->val;
        q[sum]++;
        maxCnt=max(maxCnt,q[sum]);
        return sum;
    }
    vector<int> findFrequentTreeSum(TreeNode* root) {
        tra(root);
        //排序
        vector<pair<int,int>> p(q.begin(),q.end());
        sort(p.begin(),p.end(),[](const auto& a, const auto& b)->bool{
            return a.second > b.second;
        });
        vector<int> res;
        for(auto c:p)
        {
            if(c.second==maxCnt)
                res.push_back(c.first);
        }
        return res;
    }
};