二叉树中的第 K 大层和

难度: Medium

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

Submission

运行时间: 218 ms

内存: 50.6 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
        ls=[]
        layer=[root]
        while layer:
            next_layer=[]
            cs=0
            for node in layer:
                cs+=node.val
                if node.left is not None:
                    next_layer.append(node.left)
                if node.right is not None:
                    next_layer.append(node.right)
            layer=next_layer
            ls.append(cs)
        ls.sort()
        return ls[-k] if len(ls)>=k else -1

Explain

该题解采用了层序遍历的方式来遍历二叉树，并计算每一层的节点值总和。首先，使用一个列表`layer`来存储当前层的所有节点。遍历这些节点，计算它们的值之和，并将他们的非空左右子节点添加到`next_layer`列表中。这个过程重复进行，直到没有更多的层（即`layer`为空）。所有层的和被存储在列表`ls`中。最后，将`ls`排序，并取出第`k`大的元素。如果层数少于`k`，则返回`-1`。

时间复杂度: O(n log n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
        ls=[]  # 存储每一层的和
        layer=[root]  # 当前层的节点
        while layer:
            next_layer=[]  # 下一层的节点
            cs=0  # 当前层的和
            for node in layer:
                cs+=node.val  # 累加当前层的节点值
                if node.left is not None:
                    next_layer.append(node.left)  # 添加左子节点到下一层
                if node.right is not None:
                    next_layer.append(node.right)  # 添加右子节点到下一层
            layer=next_layer  # 更新当前层
            ls.append(cs)  # 记录当前层的和
        ls.sort()  # 排序层和
        return ls[-k] if len(ls)>=k else -1  # 返回第k大的层和，如果层数不足则返回-1

Explore

是的，算法仍然正确。算法计算的是每一层所有节点值的总和，无论这些值是正数、负数还是零。然后根据求和结果进行排序和选择第K大的层和。因此，节点的正负对算法的逻辑没有影响，只会影响层和的值。

在排序层和时，如果存在相同的层和值，排序算法（如Python中的list.sort()）将会保留这些相同值的顺序关系。排序后，取第K大的层和时，算法不区分层和值是否重复。例如，如果排序后的层和列表是[10, 20, 20, 30]，第2大的层和是20，即使它与第3大的层和相同。

如果`k`大于实际的层数，即层和列表`ls`的长度小于`k`，算法将返回`-1`。这是通过检查`len(ls) >= k`来实现的。如果这个条件不满足，意味着没有足够的层来找到第K大的层和，因此返回`-1`作为错误或无效值的标记。

赋值操作`layer=next_layer`本身不会导致额外的内存使用，因为它只是将`layer`标签指向`next_layer`已经指向的对象。然而，这意味着之前`layer`指向的列表现在没有引用，将被垃圾回收。`next_layer`列表在每轮循环结束时创建新的，因此内存使用主要关乎列表中节点对象的引用数量。每次循环，旧的`next_layer`变成新的`layer`，新的`next_layer`被创建为空列表，这种方式是必须的，以确保可以探索树的下一层。