desarrollobackend.com

{ Desarrollo BACKEN:D }

BLOG

Encuentra la k-ésima Mayor Suma de Niveles en un Binary Tree

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 ? -: 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.