[LeetCode]508. The most frequent subtree elements and

subject

508.  The most frequent sub tree elements and 
 Give you a root node of binary tree  root , Please return the most frequent subtree elements and . If more than one element appears the same number of times , Returns all the most frequent subtree elements and （ Unlimited order ）.

 Of a node  「 Subtree elements and 」  It is defined as the sum of the elements of all nodes in the binary tree with the node as the root （ Including the node itself ）.

 

 Example  1：



 Input : root = [5,2,-3]
 Output : [2,-3,4]
 Example  2：



 Input : root = [5,2,-5]
 Output : [2]
 

 Tips :

 The number of nodes is  [1, 104]  Within the scope of 
-105 <= Node.val <= 105

Method 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;// Maximum number of occurrences 
// Record the current occurrence of sum  The number of times 
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;
}