二分木における K 番目に大きい合計

2583。二分木における K 番目に大きい合計

難易度: 中

トピック: ツリー、幅優先検索、並べ替え、バイナリ ツリー

二分木のルートと正の整数 k が与えられます。

ツリー内のレベル合計は、同じレベルにあるノードの値の合計です。

ツリー内の k 番目 ^の 最大 レベルの合計 (必ずしも別個である必要はありません) を返します。ツリー内のレベルが k 未満の場合は、-1 を返します。

ルートからの距離が同じであれば、2 つのノードは同じレベルにあることに注意してください。

例 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.
  • 2
  番目
  • の最大レベル合計は 13 です。

例 2:

入力:
• root = [1,2,null,3]、k = 1
出力:
• 3
説明:
• 最大のレベル合計は 3 です。

制約:

ツリー内のノードの数は n です。

• 2 5
• 1 6
• 1

ヒント:

各レベルのノードの値の合計を見つけて、k 番目に大きい値を返します。

1. 各レベルのノードの値の合計を見つけるには、DFS または BFS アルゴリズムを使用してツリーを走査し、各ノードのレベルを追跡します。

解決策:

次の手順に従います:

レベル順序トラバーサル
1. : 幅優先検索 (BFS) を使用して、ツリーをレベルごとにトラバースします。
レベル合計の計算
2. : BFS トラバーサル中に、各レベルのノード値の合計を計算します。
k 番目に大きい合計の並べ替えと検索
3. : すべてのレベルの合計を計算した後、合計を並べ替えて 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 Class

   : バイナリ ツリー内のノードを表す 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 で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が二分木における K 番目に大きい合計の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。