二叉树中第 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中文网其他相关文章！