LeetCode – Suma de subárbol más frecuente (Java)

Dada la raíz de un árbol, se le pide que encuentre la suma de subárbol más frecuente. La suma del subárbol de un nodo se define como la suma de todos los valores de nodo formados por el subárbol enraizado en ese nodo (incluido el nodo en sí). Entonces, ¿cuál es el valor de suma de subárboles más frecuente? Si hay un empate, devuelva todos los valores con la frecuencia más alta en cualquier orden.

Ejemplos 1
Aporte:

5
/
2-3

regreso [2, -3, 4], dado que todos los valores ocurren solo una vez, devuélvalos todos en cualquier orden.

Ejemplos 2
Aporte:

5
/
2-5

regreso [2], dado que 2 ocurre dos veces, sin embargo -5 solo ocurre una vez.

Solución Java

Podemos resolver este problema usando una recursividad típica en el árbol, similar a LCA.

public int[] findFrequentTreeSum(TreeNode root) {
    HashMap<Integer,Integer> map = new HashMap<>();
 
    helper(root, map);
 
    int maxCount = 0;
    for(int i: map.keySet()){
        if(map.get(i)>maxCount){
            maxCount=map.get(i);
        }
    }
 
    List<Integer> mf = new ArrayList<>();
    for(Map.Entry<Integer, Integer> entry: map.entrySet()){
        if(entry.getValue()==maxCount){
            mf.add(entry.getKey());
        }
    }
 
    int[] result = new int[mf.size()];
    int k=0;
    for(int i: mf){
        result[k++]=i;
    }
 
    return result;
}
 
public Integer helper(TreeNode root, HashMap<Integer,Integer> map){
    if(root==null){
        return null;
    }
 
    Integer left = helper(root.left, map);
    if(left==null){
        left=0;
    }
 
    Integer right = helper(root.right, map);
    if(right==null){
        right=0;
    }
 
    int sum = root.val + left + right;
    map.put(sum, map.getOrDefault(sum, 0)+1);
 
    return sum;
}

Artículos Relacionados:

Por Programación.Click

Deja una respuesta Cancelar la respuesta