[LeetCode]508. 出現次數最多的子樹元素和

題目

508. 出現次數最多的子樹元素和
給你一個二叉樹的根結點 root ，請返回出現次數最多的子樹元素和。如果有多個元素出現的次數相同，返回所有出現次數最多的子樹元素和（不限順序）。

一個結點的 「子樹元素和」 定義為以該結點為根的二叉樹上所有結點的元素之和（包括結點本身）。

 

示例 1：



輸入: root = [5,2,-3]
輸出: [2,-3,4]
示例 2：



輸入: root = [5,2,-5]
輸出: [2]
 

提示:

節點數在 [1, 104] 範圍內
-105 <= Node.val <= 105

方法1：DFS

public int[] findFrequentTreeSum(TreeNode root) {
    
    if (root == null) return new int[]{
    };
    dfs(root);
    List<Integer> list = new ArrayList<>();
    for (int k : map.keySet()) {
    
        if (map.get(k) == maxx) list.add(k);
    }
    int[] res = new int[list.size()];
    for (int i = 0; i < list.size(); i++) res[i] = list.get(i);
    return res;
}


int maxx = 0;//出現的最大的次數
//記錄當前出現的sum 的次數
Map<Integer, Integer> map = new HashMap<>();


private int dfs(TreeNode root) {
    
    if (root == null) return 0;
    int l = dfs(root.left);
    int r = dfs(root.right);
    int s = l + root.val + r;
    map.put(s, map.getOrDefault(s, 0) + 1);
    maxx = Math.max(maxx, map.get(s));
    return s;
}