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

難易度: 中

トピック: ツリー、幅優(yōu)先検索、バイナリ ツリー

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

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

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

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

例 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 を返します。
  • 必要な操作の最小數(shù)は 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 を返します。
  • 必要な操作の最小數(shù)は 3 であることが証明できます。

例 3:

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

制約:

• ツリー內(nèi)のノードの數(shù)は [1, 10⁵] の範(fàn)囲內(nèi)です。
• 1 5
• ツリーの値はすべて 一意です。

ヒント:

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

解決策:

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

重要なポイント:

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

アプローチ：

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

プラン：

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

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

<?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 を?qū)g行してノードをレベルごとにグループ化します:

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

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

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

3. サイクル分解:

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

4. スワップの合計(jì)數(shù)を返します:

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

チュートリアルの例:

例 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]

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

合計(jì)スワップ = 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] に並べ替えます。

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

出力: 3

時(shí)間計(jì)算量:

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

したがって、全體的な時(shí)間計(jì)算量は 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 を使用してレベルごとにノードをグループ化し、スワップ數(shù)を最小限に抑えるサイクル分解により、バイナリ ツリーの各レベルを並べ替えるのに必要な最小スワップ數(shù)を効率的に計(jì)算します。 O(N log N) の時(shí)間計(jì)算量は、最大 10^5 ノードを持つツリーを処理するのに最適です。

連絡(luò)先リンク

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

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

• LinkedIn
• GitHub

以上がバイナリ ツリーをレベル別にソートするための最小操作數(shù)の詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國語 Web サイトの他の関連記事を參照してください。