2583. 二叉树中的第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^5
• 1 <= Node.val <= 10^6
• 1 <= k <= n

---

解题分析及思路：

这道题考察的是二叉树的遍历，不熟悉二叉树的遍历可以查看二叉树。

方法：广度优先搜索+排序

这道题是求二叉树中的第K大层和，可以利用广度优先搜索来解决这个问题。

• 首先利用广度优先搜索来求出每一层的层和
• 然后对层和进行排序
• 最后返回第K大的层和

func kthLargestLevelSum(root *TreeNode, k int) int64 {
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	result := make([]int, 0)
	for len(queue) != 0 {
		queue1 := make([]*TreeNode, 0)
		var sum = 0
		for index := range queue {
			if queue[index] == nil {
				continue
			}
			sum += queue[index].Val
			queue1 = append(queue1, queue[index].Left)
			queue1 = append(queue1, queue[index].Right)
		}
		queue = queue1
		result = append(result, sum)
	}
	if len(result) <= k {
		return -1
	}
	sort.Ints(result)
	return int64(result[len(result)-k])
}

复杂度：

• 时间复杂度：O(N * logN)，其中 N 是树中的节点个数，O(N * logN)为排序的复杂度
• 空间复杂度：O(N)，其中 N 是树中的节点个数

执行结果：

• 执行耗时:206 ms,击败了18.68% 的Go用户
• 内存消耗:26.71 MB,击败了22.50% 的Go用户