二元樹中第 K 個最大和

2583。二元樹中第 K 個最大和

難度：中

主題：樹、廣度優先搜尋、排序、二元樹

給你一個二元樹的根和一個正整數 k。

樹中的層級總和是相同層級上的節點值的總和。

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

注意如果兩個節點到根的距離相同，則它們位於同一層級。

範例1：

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

範例2：

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

約束：

• 樹中的節點數為n。
• 2 5
• 1 6
• 1

提示：

1. 求每一層節點的值總和並回傳第k大的一個。
2. 要找到每個層級上的節點值的總和，您可以使用 DFS 或 BFS 演算法遍歷樹並追蹤每個節點的層級。

解：

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

1. 層序遍歷：我們將使用廣度優先搜尋（BFS）逐層遍歷樹。
2. 計算層級總和：在BFS遍歷過程中，我們將計算每個層級的節點值的總和。
3. 排序並找出第 k 個最大總和：計算所有層級的總和後，我們將對總和進行排序並擷取第 k 個最大值。

讓我們用 PHP 實作這個解：2583。二元樹中第 K 個最大和

<?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類別來表示二元樹中的一個節點，其中每個節點都有一個值（val）、一個左子節點（left）和一個右子節點（右）。

2. BFS 遍歷：函數 kthLargestLevelSum 使用佇列來執行 BFS 遍歷。對於每個級別，我們對節點的值求和並將結果儲存在數組中 ($levelSums)。

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

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

時間複雜度：

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

空間複雜度：

• 佇列：O(n)，用於在BFS期間儲存節點。
• 等級總和：O(m)，用於儲存每個層級的總和。
• 整體空間複雜度：O(n)。

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

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是二元樹中第 K 個最大和的詳細內容。更多資訊請關注PHP中文網其他相關文章！