Skip to content

2583. Kth Largest Sum in a Binary Tree 👍

  • Time: $O(n) \to O(n\log n)$$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  long long kthLargestLevelSum(TreeNode* root, int k) {
    vector<long> levelSums;
    dfs(root, 0, levelSums);
    if (levelSums.size() < k)
      return -1;

    nth_element(levelSums.begin(), levelSums.begin() + k - 1, levelSums.end(),
                greater<>());
    return levelSums[k - 1];
  }

 private:
  void dfs(TreeNode* root, int level, vector<long>& levelSums) {
    if (root == nullptr)
      return;
    if (levelSums.size() == level)
      levelSums.push_back(0);
    levelSums[level] += root->val;
    dfs(root->left, level + 1, levelSums);
    dfs(root->right, level + 1, levelSums);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public long kthLargestLevelSum(TreeNode root, int k) {
    List<Long> levelSums = new ArrayList<>();
    dfs(root, 0, levelSums);
    if (levelSums.size() < k)
      return -1;

    Collections.sort(levelSums, Collections.reverseOrder());
    return levelSums.get(k - 1);
  }

  private void dfs(TreeNode root, int level, List<Long> levelSums) {
    if (root == null)
      return;
    if (levelSums.size() == level)
      levelSums.add(0L);
    levelSums.set(level, levelSums.get(level) + root.val);
    dfs(root.left, level + 1, levelSums);
    dfs(root.right, level + 1, levelSums);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def kthLargestLevelSum(self, root: TreeNode | None, k: int) -> int:
    levelSums = []

    def dfs(root: TreeNode | None, level: int) -> None:
      if not root:
        return
      if len(levelSums) == level:
        levelSums.append(0)
      levelSums[level] += root.val
      dfs(root.left, level + 1)
      dfs(root.right, level + 1)

    dfs(root, 0)
    if len(levelSums) < k:
      return -1

    return sorted(levelSums, reverse=True)[k - 1]