LeetCode 题解工作台
二叉树中的第 K 大层和
给你一棵二叉树的根节点 root 和一个正整数 k 。 树中的 层和 是指 同一层 上节点值的总和。 返回树中第 k 大的层和（不一定不同）。如果树少于 k 层，则返回 -1 。 注意 ，如果两个节点与根节点的距离相同，则认为它们在同一层。 示例 1： 输入： root = [5,8,9,2,1,3…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们可以使用 BFS 遍历二叉树，同时记录每一层的节点和，然后对节点和数组进行排序，最后返回第 大的节点和即可。注意，如果二叉树的层数小于 ，则返回 。 时间复杂度 $O(n \times \log n)$，空间复杂度 。其中 为二叉树的节点数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵二叉树的根节点 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 <= 1051 <= Node.val <= 1061 <= k <= n
解题思路
方法一：BFS + 排序
我们可以使用 BFS 遍历二叉树，同时记录每一层的节点和，然后对节点和数组进行排序，最后返回第 大的节点和即可。注意，如果二叉树的层数小于 ，则返回 。
时间复杂度 ，空间复杂度 。其中 为二叉树的节点数。
# 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:
arr = []
q = deque([root])
while q:
t = 0
for _ in range(len(q)):
root = q.popleft()
t += root.val
if root.left:
q.append(root.left)
if root.right:
q.append(root.right)
arr.append(t)
return -1 if len(arr) < k else nlargest(k, arr)[-1]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N \cdot \log k) |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Candidate should demonstrate an understanding of level-order traversal and its application to binary trees.
- question_mark
The candidate should show how to handle the kth largest selection with efficient sorting or heap techniques.
- question_mark
Pay attention to how well the candidate handles edge cases such as fewer than k levels.
常见陷阱
外企场景- error
Incorrectly counting or summing nodes at each level due to improper traversal logic.
- error
Using inefficient sorting or heap techniques, leading to higher time complexity than necessary.
- error
Failing to handle the edge case where the tree has fewer than k levels, resulting in incorrect results.
进阶变体
外企场景- arrow_right_alt
Finding the kth smallest level sum instead of the kth largest.
- arrow_right_alt
Handling trees with missing nodes at certain levels (e.g., incomplete trees).
- arrow_right_alt
Optimizing space complexity when storing level sums for large trees.