给你一个二叉树的根结点,请你找出出现次数最多的子树元素和。一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和(包括结点本身)。
你需要返回出现次数最多的子树元素和。如果有多个元素出现的次数相同,返回所有出现次数最多的子树元素和(不限顺序)。
示例 1:
输入:
5
/
2 -3
返回 [2, -3, 4],所有的值均只出现一次,以任意顺序返回所有值。
示例 2:
输入:
5
/
2 -5
返回 [2],只有 2 出现两次,-5 只出现 1 次。
提示: 假设任意子树元素和均可以用 32 位有符号整数表示。
java代码:
/**
* 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 {
private Map<Integer, Integer> sumCount = new HashMap<>();
private Integer maxFrequent = Integer.MIN_VALUE;
public int[] findFrequentTreeSum(TreeNode root) {
postOrder(root);
List<Integer> help = new ArrayList<>();
// 将符合条件的所有元素和添加到 help list 当中
for (Map.Entry<Integer, Integer> next : sumCount.entrySet()) {
// 添加计数等于最大次数 maxFrequent 的 元素和
if (next.getValue() == maxFrequent) {
help.add(next.getKey());
}
}
int[] res = new int[help.size()];
for (int i = 0; i < help.size(); i++) {
res[i] = help.get(i);
}
return res;
}
private int postOrder(TreeNode node) {
// 当节点为 null, 它的元素和等于 0, 利于它的父节点进行元素和统计
if (node == null) {
return 0;
}
int left = postOrder(node.left);
int right = postOrder(node.right);
int sum = left + right + node.val;
int value = sumCount.getOrDefault(sum, 0);
sumCount.put(sum, value + 1);
maxFrequent = Math.max(maxFrequent, value + 1);
return sum;
}
}