thảo luận Leetcode mỗi ngày

class Solution {
    func kthLargestLevelSum(_ root: TreeNode?, _ k: Int) -> Int {
        var sums:[Int] = []
        func dfs(_ tree: TreeNode?, lvl: Int) {
            guard let tree else { return }
            if lvl >= sums.count {
                sums.append(tree.val)
            } else {
                sums[lvl] += tree.val
            }
            let nextLvl = lvl + 1
            dfs(tree.left, lvl: nextLvl)
            dfs(tree.right, lvl: nextLvl)
        }
        //
        dfs(root, lvl: 0)
        //
        guard k <= sums.count else { return -1}
        sums.sort(by: >)
        return sums[k-1]
    }
}

class Solution {
    public long kthLargestLevelSum(TreeNode root, int k) {
        Map<Integer,Long> sumLevel = new HashMap<>();
        dfs(root, sumLevel, 0);

        if (sumLevel.size() < k) {
            return -1;
        }
      
        PriorityQueue<Long> minHeap = new PriorityQueue<>();
        for (Map.Entry<Integer, Long> entry : sumLevel.entrySet()) {
            long sum = entry.getValue();
            if (minHeap.size() < k) {
                minHeap.add(sum);
            } else {
                if (minHeap.peek() < sum) {
                    minHeap.poll();
                    minHeap.add(sum);
                }
            }
        }

        return minHeap.peek();
    }

    public void dfs(TreeNode root, Map<Integer, Long> sumLevel, int level) {
        if (root == null) return;

        sumLevel.put(
            level, sumLevel.getOrDefault(level, 0L) + root.val
        );

        dfs(root.left, sumLevel, level + 1);
        dfs(root.right, sumLevel, level + 1);
    }
}

public long kthLargestLevelSum(TreeNode root, int k) {
        Queue<TreeNode> q = new LinkedList<>();
        List<Long> sums = new ArrayList<>();
        q.offer(root);
        while(!q.isEmpty()) {
            int size = q.size();
            long sum = 0;
            for(int i = 0; i < size; i++) {
                TreeNode tree = q.poll();
                sum += tree.val;
                if(tree.left != null) {
                    q.offer(tree.left);
                }
                if(tree.right != null) {
                    q.offer(tree.right);
                }
            }
            sums.add(sum);
        }
        if(sums.size() <= k-1) return -1;
        Collections.sort(sums, (a, b) -> b.compareTo(a));
        return sums.get(k-1);
    }

class Solution {
    public long kthLargestLevelSum(TreeNode root, int k) {
        PriorityQueue<Long> pq = new PriorityQueue<>(k,(a,b)->Long.compare(b,a));
        Queue<TreeNode> queue = new LinkedList();
        long sum = 0;
        queue.add(root);
        while(!queue.isEmpty()){
            sum = 0;
            int n = queue.size();
            for(int i = 0;i<n;i++){
                TreeNode node = queue.poll();
                sum+=node.val;
                if(node.left!=null) queue.add(node.left);
                if(node.right!=null) queue.add(node.right);               
            }
        pq.add(sum);
        if(pq.size()>k)
            pq.poll();
        }
        return pq.size()==k?pk.peek():-1;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public long kthLargestLevelSum(TreeNode root, int k) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        PriorityQueue<Long> level = new PriorityQueue<>(Collections.reverseOrder());
        while(!queue.isEmpty()) {
            int size = queue.size();
            long sum = 0l;
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                sum += curr.val;
                if (curr.left != null) {
                    queue.offer(curr.left);               
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }
            level.offer(sum);
        }
        if (level.size() < k) return -1;
        for (int i = 0; i < k - 1; i++) {
            level.poll();
        }
        return level.peek();
    }
}

    public static long KthLargestLevelSum(TreeNode root, int k)
    {
        List<long> levelSums = new List<long>();
        SumLevelRecursive(root, 0, levelSums);
        if (k >= levelSums.Count) return -1;
        levelSums.Sort(Comparer<long>.Create((x,y)=>y.CompareTo(x)));
        return levelSums[k - 1];
    }
    public static void SumLevelRecursive(TreeNode node, int levelIndex, List<long> levelSums)
    {
        if (node == null) return;
        if (levelIndex > levelSums.Count - 1) levelSums.Add(0);
        levelSums[levelIndex] += node.val;
        SumLevelRecursive(node.left, levelIndex + 1, levelSums);
        SumLevelRecursive(node.right, levelIndex + 1, levelSums);
    }

class Solution {
    public long kthLargestLevelSum(TreeNode root, int k) {
        private List<Long> lst = new ArrayList<>();
        long sum = 0L;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                TreeNode curr = q.poll();
                if (curr.left != null) q.add(curr.left);
                if (curr.right != null) q.add(curr.right);
                sum += curr.val;
            }
            lst.add(sum);
            sum = 0L;
        }
        Collections.sort(lst);
        return lst.size() < k ? -1 : lst.get(lst.size() - k);
    }
}

class Solution:
    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
        queue = deque()
        queue.append(root)

        minHeap = []

        while queue:
            lenQ = len(queue)
            currSum = 0

            for _ in range(lenQ):
                node = queue.popleft()    
                currSum += node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            heappush(minHeap, currSum)
            if len(minHeap) > k:
                heappop(minHeap)

        return heappop(minHeap) if len(minHeap) == k else -1

class Solution {
    public long kthLargestLevelSum(TreeNode root, int k) {
        Queue<Long> heap = new PriorityQueue<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);       

        while (!queue.isEmpty()) {
            long sum = 0l;
            int size = queue.size();
            System.out.println(size);
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                sum += (long) curr.val;
                if (curr.left != null) {
                    queue.add(curr.left);
                }
                if (curr.right != null) {
                    queue.add(curr.right);
                }
            }

            if (heap.size() != k) {
                heap.offer(sum);
            } else {
                if (heap.peek() < sum) {
                    heap.poll();
                    heap.offer(sum);
                }
            }
        }

        return heap.size() >= k ? heap.poll() : -1;
    }
}