<!-- prettier-ignore -->
*[BFS]: Breadth First Search

# [2583. Kth Largest Sum in a Binary Tree](https://leetcode.com/problems/kth-largest-sum-in-a-binary-tree/description/?envType=daily-question&envId=2024-10-22)

# 1. Tóm tắt đề bài

Bạn được cho gốc `root` của một cây nhị phân và một số nguyên dương $k$.

**Tổng tầng** trên một cây là tổng của tất cả các đỉnh ở **cùng một tầng** trong cây.

Hãy trả về tổng tầng lớn thứ $k$ trong cây (_tính cả những tổng tầng trùng nhau_). Nếu không tồn tại tổng tầng lớn thứ $k$, hãy trả về $-1$.

:::info
Hai đỉnh được gọi là ở **cùng một tầng** nếu đường đi từ chúng đến gốc có cùng độ dài.
:::

### Giới hạn

$n =$ Số đỉnh của cây

- $2 \le n \le 10^5$
- $1 \le$ `Node.val` $\le 10^6$
- $1 \le k \le n$

# 2. Tóm tắt lời giải

:::success
Điều kiện tiên quyết về kiến thức:

- [Cây](https://wiki.vnoi.info/vi/translate/wcipeg/tree)
- [Duyệt cây](https://wiki.vnoi.info/vi/translate/wcipeg/tree#duy%E1%BB%87t-c%C3%A2y-tree-traversal)

:::

Để tính toán tổng tầng của một cây nhị phân, ta sử dụng phương pháp duyệt cây theo tầng (Level Order Traversal).

Cách duyệt này tương tự như BFS, với sự khác biệt là tất cả những nút ở cùng một tầng sẽ được duyệt trước khi duyệt những nút ở tầng tiếp theo.

Với mỗi tầng, ta sẽ tính tổng của tất cả các nút ở tầng đó và lưu vào một mảng. Cuối cùng ta sẽ sắp xếp mảng này theo thứ tự giảm dần và trả về phần tử thứ $k$. Tất nhiên, trước đó ta kiểm tra xem mảng có đủ $k$ phần tử không, nếu không trả về $-1$.

# 3. Lời giải chi tiết

- Khởi tạo mảng `level_sums` để lưu tổng tầng của các tầng trong cây.
- Khởi tạo hàng đợi `queue` và thêm nút `root` vào hàng đợi.
- Duyệt hàng đợi theo Level Order Traversal (cho đến khi hàng đợi rỗng):
- Khởi tạo biến `level_sum` để lưu tổng tầng của tầng hiện tại.
- Khởi tạo biến `size = queue.size` là kích thước hàng đợi tại thời điểm đó, cũng chính là số nút ở tầng hiện tại.
- Lặp `size` lần:
- Lấy ra nút ở đầu hàng đợi.
- Cộng giá trị của nút vào `level_sum`.
- Nếu nút có nút con trái, thêm nút con trái vào hàng đợi.
- Nếu nút có nút con phải, thêm nút con phải vào hàng đợi.
- Thêm `level_sum` vào mảng `level_sums`.
- Nếu $k$ lớn hơn `level_sums.size`, trả về $-1$.
- Sắp xếp mảng `level_sums` theo thứ tự giảm dần và trả về phần tử thứ $k$.

### Code mẫu (Python)

# 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:
        level_sums = []
        queue = collections.deque([root])

        while queue:
            level_sum = 0

            for _ in range(len(queue)):
                node = queue.popleft()
                level_sum += node.val

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            level_sums.append(level_sum)

        return -1 if k > len(level_sums) else sorted(level_sums, reverse=True)[k - 1]

[**LeetCode Submission**](https://leetcode.com/submissions/detail/1430143884/)

### Độ phức tạp thuật toán

Thời gian: $O(n \cdot \log n)$

- Trong trường hợp tốt nhất, tổng tầng lớn thứ $k$ không tồn tại, độ phức tạp thời gian sẽ là $O(n)$.

Bộ nhớ mở rộng: $O(n)$

# 4. Kết luận & Gợi ý mở rộng

Bạn có thể giải bài này theo cách khác mà không dùng Level Order Traversal hoặc không sort mảng không?

Gợi ý mở rộng:

- [1161. Maximum Level Sum of a Binary Tree](https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/description/)
- [2641. Cousins in Binary Tree II](https://leetcode.com/problems/cousins-in-binary-tree-ii/description/)