バイナリ ツリーをレベル別にソートするための最小操作数

2471。バイナリ ツリーをレベル別にソートするための最小操作数

難易度: 中

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

一意の値を持つバイナリ ツリーのルートが与えられます。

1 回の操作で、同じレベルにある任意の 2 つのノードを選択し、それらの値を交換できます。

各レベルの値を厳密に増加する順序でソートするために必要な操作の最小数を返します。

ノードのレベルは、ノードとルート ノード間のパスに沿ったエッジの数です。

例 1:

• 入力: root = [1,4,3,7,6,8,5,null,null,null,null,9,null,10]
• 出力: 3
• 説明:
  • 4 と 3 を交換します。2 番目のレベルは [3,4] になります。
  • 7 と 5 を交換します。3 番目のレベルは [5,6,8,7] になります。
  • 8 と 7 を交換します。3 番目のレベルは [5,6,7,8] になります。
  • 3 つの操作を使用したため、3 を返します。
  • 必要な操作の最小数は 3 であることが証明できます。

例 2:

• 入力: root = [1,3,2,7,6,5,4]
• 出力: 3
• 説明:
  • 3 と 2 を交換します。2 番目のレベルは [2,3] になります。
  • 7 と 4 を交換します。3 番目のレベルは [4,6,5,7] になります。
  • 6 と 5 を交換します。3 番目のレベルは [4,5,6,7] になります。
  • 3 つの操作を使用したため、3 を返します。
  • 必要な操作の最小数は 3 であることが証明できます。

例 3:

• 入力: root = [1,2,3,4,5,6]
• 出力: 0
• 説明: 各レベルはすでに昇順にソートされているため、0 を返します。

制約:

• ツリー内のノードの数は [1, 10⁵] の範囲内です。
• 1 5
• ツリーの値はすべて 一意です。

ヒント:

1. 値をレベルごとにグループ化し、各グループを個別に解決できます。
2. BFS を実行して値レベルをレベルごとにグループ化します。
3. 各レベルの配列をソートするためのスワップの最小数を見つけます。
4. 配列を反復処理する際に、現在の要素をチェックし、正しいインデックスにない場合は、その要素を本来あるべき要素のインデックスに置き換えます。

解決策:

問題は、最小限の操作でバイナリ ツリーの値をレベルごとに厳密に昇順に並べ替えることです。各操作で、同じレベルにある 2 つのノードの値を交換できます。目標は、並べ替え順序を達成するために必要なこのような操作の最小数を決定することです。

重要なポイント:

1. バイナリ ツリー レベル: バイナリ ツリーの各レベルには、厳密に昇順に並べ替えられた値が含まれている必要があります。
2. 一意の値: すべてのノードには一意の値があり、重複がないため並べ替えが容易になります。
3. レベル グループ化の BFS: 幅優先検索 (BFS) を使用してツリーを横断し、レベルごとにノードをグループ化します。
4. 最小スワップ: 各レベルについて、そのレベルでノード値を並べ替えるのに必要な最小スワップ数を見つける必要があります。
5. 制約: ツリーには最大 10^5 ノードを含めることができるため、ソリューションは効率的である必要があります。

アプローチ：

1. BFS トラバーサル: BFS を実行してツリーをトラバースし、各レベルのノードの値を収集します。
2. 各レベルの並べ替え: レベルごとに、値を厳密に昇順に並べ替えるための最小スワップ数を計算します。
3. サイクル分解: スワップを最小限に抑えるための重要な観察は、配列のソートがサイクル内の要素のスワップと見なされるということです。間違って配置された要素の各サイクルのスワップの最小数は、サイクルの長さから 1 を引いたものです。
4. スワップの累積: 各レベルのスワップを合計して、必要なスワップの合計数を取得します。

プラン：

1. BFS: BFS を使用してツリーを走査し、各レベルでノードを収集します。
2. 各レベルの並べ替え: 各レベルで値を並べ替え、最小スワップ数を計算します。
3. スワップの計算: サイクル分解を使用して、各レベルでノードを並べ替えるのに必要な最小スワップを見つけます。

このソリューションを PHP で実装してみましょう: 2471。バイナリ ツリーをレベル別にソートするための最小操作数

<?php /**
 * @param TreeNode $root
 * @return Integer
 */
function minimumOperations($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to calculate minimum swaps to sort an array
 *
 * @param $arr
 * @return int
 */
function minSwapsToSort($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
?>

説明：

1. ステップ 1: BFS を実行してノードをレベルごとにグループ化します:

   • ルートから開始して、ツリーをレベルごとに移動します。
   • 各ノードについて、その値をレベル配列の対応するレベルに追加します。

2. ステップ 2: レベルごとに、値を並べ替えるための最小スワップを計算します:

   • 各レベルで値を並べ替えます。
   • サイクルベースのアプローチを使用して、現在のレベルをソートされたレベルに変換するために必要な最小スワップを計算します。

3. サイクル分解:

   • ソートされていない各要素について、そのサイクル (つまり、どこへ行くべきか) を追跡し、要素を訪問済みとしてマークします。
   • 各サイクルで必要なスワップ数は、サイクルの長さから 1 を引いたものになります。

4. スワップの合計数を返します:

   • 各レベルに必要なスワップを合計し、合計を返します。

チュートリアルの例:

例 1:

入力ツリー:

<?php /**
 * @param TreeNode $root
 * @return Integer
 */
function minimumOperations($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to calculate minimum swaps to sort an array
 *
 * @param $arr
 * @return int
 */
function minSwapsToSort($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
?>

レベル:

• レベル 0: [1]
• レベル 1: [4, 3]
• レベル 2: [7、6、8、5]
• レベル 3: [9、10]

1. レベル 1: [4, 3]

   • 1 回の交換で [3, 4] にソートします (4 と 3 を交換)。

2. レベル 2: [7, 6, 8, 5]

   • 2 回の入れ替え (7 と 5 の入れ替え、8 と 7 の入れ替え) で [5, 6, 7, 8] に並べ替えます。

3. レベル 3: [9, 10]

   • すでにソートされているため、交換する必要はありません。

合計スワップ = 1 (レベル 1) 2 (レベル 2) = 3 スワップ。

出力: 3

例 2:

入力ツリー:

        1
       / \
      4   3
     / \ / \
    7  6 8  5
             \
              9
               \
                10

レベル:

• レベル 0: [1]
• レベル 1: [3, 2]
• レベル 2: [7、6、5、4]

1. レベル 1: [3, 2]

   • 1 回の交換で [2, 3] にソートします (3 と 2 を交換)。

2. レベル 2: [7, 6, 5, 4]

   • 2 回の入れ替え (7 と 4 の入れ替え、6 と 5 の入れ替え) で [4, 5, 6, 7] に並べ替えます。

合計スワップ = 1 (レベル 1) 2 (レベル 2) = 3 スワップ。

出力: 3

時間計算量:

1. BFS: O(N) ここで、N はツリー内のノードの数です。
2. 各レベルの並べ替え: 各レベルでの値の並べ替えには O(L log L) がかかります。L は現在のレベルのノードの数。最悪の場合、ソートの総複雑さは O(N log N).
になります。
3. サイクル分解: 各レベルの O(L)。

したがって、全体的な時間計算量は O(N log N) となり、制約を考慮すると十分効率的です。

出力例:

入力ツリーの場合:

<?php /**
 * @param TreeNode $root
 * @return Integer
 */
function minimumOperations($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to calculate minimum swaps to sort an array
 *
 * @param $arr
 * @return int
 */
function minSwapsToSort($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
?>

例で詳しく説明されているように、出力は 3 つのスワップです。

このソリューションは、BFS を使用してレベルごとにノードをグループ化し、スワップ数を最小限に抑えるサイクル分解により、バイナリ ツリーの各レベルを並べ替えるのに必要な最小スワップ数を効率的に計算します。 O(N log N) の時間計算量は、最大 10^5 ノードを持つツリーを処理するのに最適です。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上がバイナリ ツリーをレベル別にソートするための最小操作数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。