算法 - 【二叉树中的第 K 大层和】

本文主要是介绍算法 - 【二叉树中的第 K 大层和】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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

这篇关于算法 - 【二叉树中的第 K 大层和】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---