508.出现次数最多的子树元素和(二叉树，哈希表，中等)

题目链接

给你一个二叉树的根结点，请你找出出现次数最多的子树元素和。一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

你需要返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

示例 1：

输入:

  5
 /  \
2   -3
返回 [2, -3, 4]，所有的值均只出现一次，以任意顺序返回所有值。

示例 2：

输入：

  5
 /  \
2   -5
返回 [2]，只有 2 出现两次，-5 只出现 1 次。

提示：假设任意子树元素和均可以用 32 位有符号整数表示。

解答

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int[] findFrequentTreeSum(TreeNode root) {
        // 1.计算所有子树元素和(深度优先搜索法)
        List<Integer> treeSumList = new ArrayList<>();
        getTreeSumList(root, treeSumList);
        // 2.取出数组中出现次数最多的元素，用map结构存储出现的元素与其出现次数的对应关系
        Map<Integer, Integer> occurCountMap = new HashMap<>();
        for (int treeSum : treeSumList)
            occurCountMap.put(treeSum, occurCountMap.getOrDefault(treeSum, 0)+1);
        List<Integer> resultList = new ArrayList<>();
        // 统计出现次数最多的子树元素和次数，动态维护子树元素和值
        int maxCount = 0, value;
        for (int key : occurCountMap.keySet()) {
            if ((value = occurCountMap.get(key)) > maxCount) {
                resultList.clear();
                resultList.add(key);
                maxCount = value;
            } else if (value == maxCount) {
                resultList.add(key);
            }
        }
        int[] result = new int[resultList.size()];
        for (int i = 0; i < result.length; i++)
            result[i] = resultList.get(i);
        return result;
    }

    // 获取root为根节点下的所有子树元素和
    public int getTreeSumList(TreeNode root, List<Integer> treeSumList) {
        if (root == null) return 0;
        int leftTreeSum = 0, rightTreeSum = 0, treeSum;
        if (root.left != null) leftTreeSum = getTreeSumList(root.left, treeSumList);
        if (root.right != null) rightTreeSum = getTreeSumList(root.right, treeSumList);
        treeSumList.add(treeSum = leftTreeSum+rightTreeSum+root.val);
        return treeSum;
    }
}