给你一个二叉树的根结点，请你找出出现次数最多的子树元素和。一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。
你需要返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
示例 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;
}
}
