1.题目描述
给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。
示例 1：
输入: root = [5,2,-3]
输出: [2,-3,4]
示例 2：
输入: root = [5,2,-5]
输出: [2]
2.解题思路与代码
2.1 解题思路
这道题首先需要求出每个子树的和，然后统计出出现次数最多的和。统计子树和时，使用递归进行遍历，首先计算左子树的和，然后计算右子树的和，最后将左子树和、右子树和与当前节点的值相加得当以当前节点为根的子树子树之和。使用一个 Map 存放子树和与个数的关系， key 是子树之和，value 是该值总共出现的次数。并且使用 max 变量存放最大出现次数。遍历完成之后再对 map 进行遍历，出现次数等于 max 的数字放入列表中，最后将列表转为数组返回。
2.2 代码
class Solution {
// 存放子树和与出现次数的映射
Map<Integer, Integer> map = new HashMap<>();
// 最大出现次数
int max = Integer.MIN_VALUE;
public int[] findFrequentTreeSum(TreeNode root) {
process(root);
// 由于出现次数不知道等于 max 的和有多少个，因此先使用列表暂存，最后转换为数组再返回
List<Integer> tmp = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() == max) {
tmp.add(entry.getKey());
}
}
int[] ans = new int[tmp.size()];
for (int i = 0; i < ans.length; i++) {
ans[i] = tmp.get(i);
}
return ans;
}
public int process(TreeNode root) {
if (root == null) {
return 0;
}
// 递归计算左子树之和
int left = process(root.left);
// 递归计算右子树之和
int right = process(root.right);
// 计算以当前节点为根的子树之和
int sum = left + right + root.val;
// 计算结果存入 map 并计算出现的最大次数
Integer count = map.merge(sum, 1, Integer::sum);
max = Math.max(max, count);
return sum;
}
}
2.3 测试结果
通过测试
测试结果
3.总结
- 题目首先是需要计算每个子树之后，然后统计出现次数最多的子树和
- 使用递归以当前节点为根的子树之后，然后使用 map 存放出现次数，同时使用 max 统计子树和出现最多的次数
