[leetcode] 508. Élément de sous - arbre le plus fréquent et

Titre

508. Les éléments du sous - arbre les plus fréquents et
Pour vous donner un noeud racine d'arbre binaire root ,Veuillez retourner l'élément sous - arbre qui apparaît le plus souvent et.Si plus d'un élément apparaît le même nombre de fois,Renvoie tous les éléments du sous - arbre les plus fréquents et（Ordre illimité）.

Un noeud 「Élément de sous - arbre et」 Défini comme la somme des éléments de tous les noeuds d'un arbre binaire dont le noeud est la racine（Y compris le noeud lui - même）.

 

Exemple 1：



Entrée: root = [5,2,-3]
Produits: [2,-3,4]
Exemple 2：



Entrée: root = [5,2,-5]
Produits: [2]
 

Conseils:

Nombre de noeuds [1, 104] Dans le champ d'application
-105 <= Node.val <= 105

Méthodes1：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;// Nombre maximum d'occurrences 
// Enregistrer ce qui se passe actuellement sum Nombre de fois
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;
}