【Lintcode】1198. Most Frequent Subtree Sum

题目地址：

https://www.lintcode.com/problem/most-frequent-subtree-sum/description

给定一棵二叉树，每个子树有一个节点和（即该子树的所有节点之和），问出现最多次数的和是多少。如果有出现次数相等的，则每个和都要返回。

思路是DFS + 哈希表。DFS的同时用哈希表来累加当前节点子树和出现的次数。最后归总一下即可。代码如下：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;public class Solution {
    /*** @param root: the root* @return: all the values with the highest frequency in any order*/public int[] findFrequentTreeSum(TreeNode root) {
    // Write your code hereMap<Integer, Integer> map = new HashMap<>();dfs(root, map);List<Integer> list = new ArrayList<>();int max = 0;for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
    int key = entry.getKey(), val = entry.getValue();// 如果列表空或者val刚好等于max，说明max子树和又出现了一次if (list.isEmpty() || val == max) {
    list.add(key);max = val;} else if (val > max) {
    // 出现了更多次数的子树和，需要清空列表list.clear();list.add(key);max = val;}}int[] res = new int[list.size()];for (int i = 0; i < list.size(); i++) {
    res[i] = list.get(i);}return res;}private int dfs(TreeNode cur, Map<Integer, Integer> map) {
    if (cur == null) {
    return 0;}int sum = cur.val;sum += dfs(cur.left, map) + dfs(cur.right, map);map.put(sum, map.getOrDefault(sum, 0) + 1);return sum;}
}class TreeNode {
    int val;TreeNode left, right;public TreeNode(int val) {
    this.val = val;}
}

时空复杂度$O(n)$。