刷题

一、题目描述：

给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

示例 1：

输入: root = [5,2,-3]
输出: [2,-3,4]
示例 2：

输入: root = [5,2,-5]
输出: [2]

提示:

节点数在 [1, 104] 范围内
-105 <= Node.val <= 105

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/most-frequent-subtree-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思路分析：

在统计所有子树和时，可以使用最朴素的递归方式。
递归函数内需要同时完成以下两个任务：

计算以当前节点为根的子树和，并加入统计结果。
返回以当前节点为根的子树和，方便父节点递归调用。
有了子树和及其计数后，只需遍历统计结果一次，实时维护拥有最大计数的列表即可。

三、AC 代码：

class Solution {
    public int[] findFrequentTreeSum(TreeNode root) {
        HashMap<Integer, Integer> sum_2_cnt = new HashMap<>();
        countSum(root, sum_2_cnt);
        List<Integer> resList = new ArrayList<>();
        int maxCnt = -1;
        for(int sum : sum_2_cnt.keySet()) {
            int cnt = sum_2_cnt.get(sum);
            if(cnt>maxCnt) {
                resList.clear();
                resList.add(sum);
                maxCnt = cnt;
            }else if(cnt==maxCnt) {
                resList.add(sum);
            }
        }
        int[] res = new int[resList.size()];
        for(int i=0; i<res.length; i++) {
            res[i] = resList.get(i);
        }
        return res;
    }
    
    private int countSum(TreeNode cur, HashMap<Integer, Integer> sum_2_cnt) {
        if(cur==null) return 0;
        int left = countSum(cur.left, sum_2_cnt);
        int right = countSum(cur.right, sum_2_cnt);
        int sum = left + right + cur.val;
        sum_2_cnt.put(sum, sum_2_cnt.getOrDefault(sum, 0)+1);
        return sum;
    }
}

四、总结：

掘友们，解题不易，留下个赞或评论再走吧！谢啦~ 💐

希望对你有帮助