문제

You are given the root of a binary tree and a positive integer k.

The level sum in the tree is the sum of the values of the nodes that are on the same level.

Return the kth largest level sum in the tree (not necessarily distinct). If there are fewer than k levels in the tree, return -1.

Note that two nodes are on the same level if they have the same distance from the root.

요약

같은 depth에서 총 합의 크기가 k번째가 되는 값을찾는 문제이다.

풀이

트리를 활용한 dfs 문제이다.

코드


/**
 * 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;
 *     }
 * }
 */
import java.util.*;

class Solution {
    public long kthLargestLevelSum(TreeNode root, int k) {
        Queue<LevelNode> queue = new LinkedList<>();
        long[] sum = new long[10_0001];
        int maxLevel = 0;
        long result = 0;
        queue.offer(new LevelNode(root, 1));
        while (!queue.isEmpty()) {
            LevelNode now = queue.poll();
            TreeNode node = now.node;
            int level = now.level;
            maxLevel = Math.max(level, maxLevel);
            sum[level] += node.val;
            result = Math.max(result, sum[level]);
            if (node.right != null) {
                queue.add(new LevelNode(node.right, level + 1));
            }
            if (node.left != null) {
                queue.add(new LevelNode(node.left, level + 1));
            }
        }
        if (maxLevel < k) {
            return -1;
        }
        PriorityQueue<Long> pq = new PriorityQueue<>((o1,o2) -> Long.compare(o2,o1));
        for (int i = 1; i <= maxLevel ; i ++) {
            pq.offer(sum[i]);
        }
        for (int i = 0; i < k; i ++) {
            result = pq.poll();
        }
        return result;
    }

    private class LevelNode {
        TreeNode node;
        int level;

        private LevelNode(TreeNode node, int level) {
            this.node = node;
            this.level = level;
        }
    }
}

풀이 시간

20min

체감 난이도

백준기준 실버 3?