En este artículo, abordaremos el problema de encontrar la k-ésima mayor suma de niveles en un binary tree. Este problema es un desafío común en entrevistas técnicas y plataformas como LeetCode.
Descripción del Problema
Dado el nodo raíz de un binary tree y un entero positivo k, debe encontrar la k-ésima mayor suma de nodos que están en el mismo nivel. Si hay menos de k niveles, debería retornar -1.
Solución en Java
A continuación, se presenta una solución implementada en Java:
import java.util.*;
public class KthLargestLevelSum {
public static int kthLargestLevelSum(TreeNode root, int k) {
if (root == null) return -1;
Queue<TreeNode> queue = new LinkedList<>();
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
int levelSum = 0;
for (int i = 0; i < levelSize; i++) {
TreeNode currentNode = queue.poll();
levelSum += currentNode.val;
if (currentNode.left != null) queue.offer(currentNode.left);
if (currentNode.right != null) queue.offer(currentNode.right);
}
if (minHeap.size() < k) {
minHeap.offer(levelSum);
} else if (levelSum > minHeap.peek()) {
minHeap.poll();
minHeap.offer(levelSum);
}
}
return minHeap.size() < k ? -1 : minHeap.peek();
}
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
}
Explicación de la Solución
La solución emplea una técnica de Breadth-First Search (BFS) para recorrer el árbol nivel por nivel y calcular la suma de nodos en cada nivel. Luego, utiliza una estructura de datos adecuada para mantener las k mayores sumas de niveles encontradas hasta el momento.
Conclusión
Con esta implementación, podrás resolver eficientemente el problema de la k-ésima mayor suma de niveles en un binary tree. Para más soluciones a problemas comunes de programación en Java, sigue explorando nuestro contenido.