2583。二元樹中第 K 個(gè)最大和

難度：中

主題：樹、廣度優(yōu)先搜尋、排序、二元樹

給你一個(gè)二元樹的根和一個(gè)正整數(shù) k。

樹中的層級(jí)總和是相同層級(jí)上的節(jié)點(diǎn)值的總和。

返回樹中第k^第 最大級(jí)總和（不一定不同）。如果樹中的層數(shù)少於 k，則回傳 -1.

注意如果兩個(gè)節(jié)點(diǎn)到根的距離相同，則它們位於同一層級(jí)。

範(fàn)例1：

• 輸入： root = [5,8,9,2,1,3,7,4,6??], k = 2
• 輸出： 13
• 說明：等級(jí)總和如下：
  • 1 級(jí)：5。
  • 2 級(jí)：8 9 = 17。
  • 第 3 級(jí)：2 1 3 7 = 13。
  • 4 級(jí)：4 6 = 10。
  • 第二個(gè)^第最大等級(jí)總和是13。

範(fàn)例2：

• 輸入： root = [1,2,null,3], k = 1
• 輸出： 3
• 說明：最大等級(jí)總和為 3。

約束：

• 樹中的節(jié)點(diǎn)數(shù)為n。
• 2 5
• 1 6
• 1

提示：

1. 求每一層節(jié)點(diǎn)的值總和並回傳第k大的一個(gè)。
2. 要找到每個(gè)層級(jí)上的節(jié)點(diǎn)值的總和，您可以使用 DFS 或 BFS 演算法遍歷樹並追蹤每個(gè)節(jié)點(diǎn)的層級(jí)。

解：

我們將按照以下步驟操作：

1. 層序遍歷：我們將使用廣度優(yōu)先搜尋（BFS）逐層遍歷樹。
2. 計(jì)算層級(jí)總和：在BFS遍歷過程中，我們將計(jì)算每個(gè)層級(jí)的節(jié)點(diǎn)值的總和。
3. 排序並找出第 k 個(gè)最大總和：計(jì)算所有層級(jí)的總和後，我們將對(duì)總和進(jìn)行排序並擷取第 k 個(gè)最大值。

讓我們用 PHP 實(shí)作這個(gè)解：2583。二元樹中第 K 個(gè)最大和

<?php
// Definition for a binary tree node.
class TreeNode {
    public $val;
    public $left;
    public $right;
    public function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

/**
 * @param TreeNode $root
 * @param Integer $k
 * @return Integer
 */
function kthLargestLevelSum($root, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1:
// Input: root = [5,8,9,2,1,3,7,4,6], k = 2
$root1 = new TreeNode(5);
$root1->left = new TreeNode(8);
$root1->right = new TreeNode(9);
$root1->left->left = new TreeNode(2);
$root1->left->right = new TreeNode(1);
$root1->right->left = new TreeNode(3);
$root1->right->right = new TreeNode(7);
$root1->left->left->left = new TreeNode(4);
$root1->left->left->right = new TreeNode(6);
echo kthLargestLevelSum($root1, 2); // Output: 13

// Example 2:
// Input: root = [1,2,null,3], k = 1
$root2 = new TreeNode(1);
$root2->left = new TreeNode(2);
$root2->left->left = new TreeNode(3);
echo kthLargestLevelSum($root2, 1); // Output: 3
?>

解釋：

1. TreeNode類別：我們定義TreeNode類別來表示二元樹中的一個(gè)節(jié)點(diǎn)，其中每個(gè)節(jié)點(diǎn)都有一個(gè)值（val）、一個(gè)左子節(jié)點(diǎn)（left）和一個(gè)右子節(jié)點(diǎn)（右）。

2. BFS 遍歷：函數(shù) kthLargestLevelSum 使用佇列來執(zhí)行 BFS 遍歷。對(duì)於每個(gè)級(jí)別，我們對(duì)節(jié)點(diǎn)的值求和並將結(jié)果儲(chǔ)存在數(shù)組中 ($levelSums)。

3. 對(duì)層級(jí)總和進(jìn)行排序：遍歷整棵樹併計(jì)算層級(jí)總和後，我們使用 rsort 對(duì)總和進(jìn)行降序排序。這使我們能夠輕鬆獲得第 k 大的總和。

4. 邊緣情況處理：如果少於 k 個(gè)級(jí)別，我們返回 -1。

時(shí)間複雜度：

• BFS 遍歷：O(n)，其中 n 是樹中的節(jié)點(diǎn)數(shù)。
• 排序：O(m log m)，其中m是樹中的層數(shù)。由於 m 遠(yuǎn)小於 n，因此排序速度相對(duì)較快。
• 總體時(shí)間複雜度：O(n m log m)。

空間複雜度：

• 佇列：O(n)，用於在BFS期間儲(chǔ)存節(jié)點(diǎn)。
• 等級(jí)總和：O(m)，用於儲(chǔ)存每個(gè)層級(jí)的總和。
• 整體空間複雜度：O(n)。

這種方法確保我們有效地遍歷樹並返回正確的第k^第 最大等級(jí)總和。

聯(lián)絡(luò)連結(jié)

如果您發(fā)現(xiàn)本系列有幫助，請(qǐng)考慮在 GitHub 上給 存儲(chǔ)庫(kù) 一個(gè)星號(hào)或在您最喜歡的社交網(wǎng)絡(luò)上分享該帖子？ 。您的支持對(duì)我來說意義重大！

如果您想要更多類似的有用內(nèi)容，請(qǐng)隨時(shí)關(guān)注我：

• 領(lǐng)英
• GitHub

以上是二元樹中第 K 個(gè)最大和的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！