# LeetCode 2583. Kth Largest Sum in a Binary Tree

https://leetcode.com/problems/kth-largest-sum-in-a-binary-tree/description/

## 題目大意

給定二元樹及正整數 `k`

level sum 指二元樹同一 level (如果你不知道，節點到 `root` 的距離相同表示在同一 level) 的節點值總和，求這第 `k` 大的
如果樹少於 `k` level 回傳 `-1`

題目保證樹中至少 `2` 個節點並且 `k` 不會超過節點總數 (樹高最高的情況即斜曲的二元樹，如果 `k` 比節點總數還大，那肯定不會有該 level)

## 思考

這題算資料結構挺經典的問題類型了吧，不過我們沒辦法去修改 `TreeNode` 所以我覺得這題沒什麼好講的了，就把樹走訪一遍後排出第 `k` 大

以下 C++ 參考解答，使用 `std::nth_element` ，不必把整個 `levelSums` 都做好排序

class Solution
{
public:
    long long kthLargestLevelSum(TreeNode *root, int k)
    {
        vector<long> levelSums;
        queue<TreeNode *> q;
        q.push(root);

        while (!q.empty())
        {
            int sz = q.size();
            long levelSum = 0;

            while (sz--)
            {
                TreeNode *node = q.front();
                q.pop();

                levelSum += node->val;

                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
            }

            levelSums.push_back(levelSum);
        }

        if (levelSums.size() < k)
            return -1;

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

        return levelSums[k - 1];
    }
};

Go 的參考解答：

func kthLargestLevelSum(root *TreeNode, k int) int64 {
	var levelSums []int64
	q := []*TreeNode{root}

	for len(q) > 0 {
		sz := len(q)
		var levelSum int64 = 0

		for i := 0; i < sz; i++ {
			node := q[0]
			q = q[1:]
			levelSum += int64(node.Val)

			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
		}

		levelSums = append(levelSums, levelSum)
	}

	if len(levelSums) >= k {
		sort.Slice(levelSums, func(i, j int) bool {
			return levelSums[i] > levelSums[j]
		})
		return levelSums[k-1]
	}
	return -1
}