题目描述

给你一棵二叉树的根节点 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 。

解题思路 

本题思路其实是比较简单的，首先我们需要思考题目的意思，题目要求我们求出层的数值和，而我们要得到数值的和显然需要进行一次bfs，然后将数存储在一个结构当中，我想到优先队列可以维护出一个有序队列，于是我使用优先队列进行排序，而后第几就是将优先队列书城几个返回就可以了。

代码如下

class Solution {public long kthLargestLevelSum(TreeNode root, int k) {PriorityQueue<Long> pq = new PriorityQueue<Long>();Queue<TreeNode> q=new LinkedList<>();int l=0;q.add(root);while(!q.isEmpty()){int n=q.size();long lo=0L;l++;while(n-->0){TreeNode t=q.poll();lo+=t.val;if(t.left!=null)q.offer(t.left);if(t.right!=null)q.offer(t.right);}pq.add(lo);}if(l<k)return -1L;for(int i=0;i<l-k;i++)//因为是从小到大，所以我用层减去第几pq.poll();return pq.poll();}
}

但是测试结果其实并不理想，后来我发现，这样很容易退化为On，因为如果要求我们得到最大值时，我们需要遍历全部，效果不佳，其实反而不如直接排序然后再获取第几个位置显得有效。