。各ツリー行の最大値を見つける

515。各ツリー行の最大値を見つける

難易度: 中

トピック: ツリー、深さ優先検索、幅優先検索、バイナリ ツリー

バイナリ ツリーのルートを指定すると、ツリーの各行の最大値の配列 (0 からインデックス付き)を返します。

例 1:

• 入力: root = [1,3,2,5,3,null,9]
• 出力: [1,3,9]

例 2:

• 入力: root = [1,2,3]
• 出力: [1,3]

制約:

• ツリー内のノードの数は [0, 10⁴] の範囲になります。
• -2³¹ <= Node.val <= 2³¹ - 1

解決策:

問題 「各ツリー行の最大値を見つける」 では、バイナリ ツリーの各レベル (行) に存在する最大値を特定する必要があります。バイナリ ツリーが与えられた場合、目標はツリーを行ごとに走査し、各行から最大値を収集することです。この問題には、幅優先検索 (BFS) や 深さ優先検索 (DFS) などの基本的なツリー トラバーサル手法が関係します。

重要なポイント

1. ツリー トラバーサル: この解決策には、バイナリ ツリーのすべてのレベルを走査して、各レベルの最大値を特定することが含まれます。
2. 幅優先検索 (BFS): BFS はレベルごとの走査に適しており、各行の最大値の検索が簡素化されます。
3. 制約: 空のツリーや、制約範囲内の大きいまたは小さい整数値を持つノードなどのエッジ ケースを処理します。

アプローチ

各行の最大値を見つける最も簡単な方法は、BFS:

を使用することです。

• ツリーをレベルごとに移動します。
• レベルごとに、最大値を記録します。

代わりに、DFS も使用できます。

• ツリーを再帰的に走査し、各深さの最大値の記録を維持します。

計画

1. 各行の最大値を格納するために配列を初期化します。
2. BFS トラバーサルにキューを使用します。
   • ルートノードから始めます。
   • 次のレベルに進む前に、現在のレベルですべてのノードを処理します。
3. 各レベル:
   • すべてのノードを反復処理し、最大値を見つけます。
   • この値を結果配列に追加します。
4. 走査の完了後に結果の配列を返します。

解決策の手順

1. 入力のチェック: ルートが null の場合は、空の配列を返します。
2. BFS のセットアップ:
   • ルート ノードで初期化されたキューを使用します。
   • 空の結果配列を初期化します。
3. トラバースレベル:
   • レベルごとに最大値を追跡します。
   • 次のレベルのキューに子ノードを追加します。
4. 結果を更新:
   • 各レベルの最大値を結果の配列に追加します。
5. 結果を返す: 各行の最大値を含む結果配列を返します。

このソリューションを PHP で実装してみましょう: 515。各ツリー行の最大値を検索

val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

/**
 * @param TreeNode $root
 * @return Integer[]
 */
function largestValues($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$root = new TreeNode(1);
$root->left = new TreeNode(3);
$root->right = new TreeNode(2);
$root->left->left = new TreeNode(5);
$root->left->right = new TreeNode(3);
$root->right->right = new TreeNode(9);

print_r(largestValues($root)); // Output: [1, 3, 9]
?>





  
  
  説明：



  
  
  入力: [1,3,2,5,3,null,9]




レベル 0: ノード値: [1] → 最大: 1.

レベル 1: ノード値: [3, 2] → 最大: 3.

レベル 2: ノード値: [5, 3, 9] → 最大: 9。
#### 出力: [1, 3, 9].



  
  
  時間計算量




BFS トラバーサル: 各ノードは 1 回処理されます → O(n).

最大値の探索: トラバース中に実行 → レベルごとに O(1)。

合計: O(n).



  
  
  空間の複雑さ




キューストレージ: 最大でツリーの幅 (最大レベルのノード数) → O(w) ここで、w はツリーの最大幅です。



  
  
  出力例


入力: root = [1,3,2,5,3,null,9]


出力: [1, 3, 9].

この BFS ベースのソリューションは、線形時間計算量でツリーの各行の最大値を効率的に計算します。大きなツリー、負の値、空のツリーなどの特殊なケースを効果的に処理します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

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

LinkedIn
GitHub



          

            
  

            
        
以上が。各ツリー行の最大値を見つけるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。