题目

给你一棵二叉树的根节点 root 和一个正整数 k 。树中的层和是指同一层上节点值的总和。返回树中第 k 大的层和（不一定不同）。如果树少于 k 层，则返回 -1 。注意，如果两个节点与根节点的距离相同，则认为它们在同一层。

示例1

输入：root = [5,8,9,2,1,3,7,4,6], k = 2
输出：13
解释：树中每一层的层和分别是：
Level 1: 5
Level 2: 8 + 9 = 17
Level 3: 2 + 1 + 3 + 7 = 13
Level 4: 4 + 6 = 10
第 2 大的层和等于 13 。

示例2

输入：root = [1,2,null,3], k = 1
输出：3
解释：最大的层和是 3 。

• 树中的节点数为 n
• 2 <= n <= 10⁵
• 1 <= Node.val <= 10⁶
• 1 <= k <= n

分析

返回的是第k大的层和，可以使用 BFS 计算每一层节点的和，然后对这些和从大到小排序，最后取出第k个值即可。
二叉树的 BFS 遍历需要使用一个队列来记录每层的节点，当遍历队列中节点的时候需要累加当前层的和，顺便把下一层的节点也添加到队列中。

代码

public long kthLargestLevelSum(TreeNode root, int k) {
    List<Long> mList = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<>();// 创建队列
    q.offer(root);// 根节点添加到队列中
    while (!q.isEmpty()) {
        int size = q.size();// 当前层的节点个数
        long sum = 0;// 当前层所有节点的和
        while (size-- > 0) {
            TreeNode cur = q.poll();// 出队
            sum += cur.val;// 累加当前层节点的值
            // 当前节点的左右子树如果不为空，也添加到队列中
            if (cur.left != null) q.offer(cur.left);
            if (cur.right != null) q.offer(cur.right);
        }
        mList.add(sum);// 当前层的和计算完之后添加到list中
    }
    if (mList.size() < k)// 如果少于k层，返回-1。
        return -1;
    // 从大到小排序，然后取出第k个元素
    Collections.sort(mList, (a, b) -> Long.compare(b, a));
    return mList.get(k - 1);
}