Mindestanzahl von Operationen zum Sortieren eines Binärbaums nach Ebene

2471. Mindestanzahl von Operationen zum Sortieren eines Binärbaums nach Ebene

Schwierigkeit:Mittel

Themen: Baum, Breitensuche, Binärbaum

Sie erhalten die Wurzel eines Binärbaums mit einzigartigen Werten.

In einem Vorgang können Sie zwei beliebige Knoten auf derselben Ebene auswählen und ihre Werte austauschen.

Gib die Mindestanzahl an Operationen zurück, die erforderlich sind, um die Werte auf jeder Ebene in einer streng aufsteigenden Reihenfolge zu sortieren.

Die Ebene eines Knotens ist die Anzahl der Kanten entlang des Pfades zwischen ihm und dem Wurzelknoten.

Beispiel 1:

• Eingabe: root = [1,4,3,7,6,8,5,null,null,null,null,9,null,10]
• Ausgabe: 3
• Erklärung:
  • Tauschen Sie 4 und 3. Die 2. Ebene wird zu [3,4].
  • Tausch 7 und 5. Die 3. Ebene wird zu [5,6,8,7].
  • Vertauschen Sie 8 und 7. Die 3. Ebene wird zu [5,6,7,8].
  • Wir haben 3 Operationen verwendet, also geben wir 3 zurück.
  • Es kann nachgewiesen werden, dass 3 die Mindestanzahl der erforderlichen Operationen ist.

Beispiel 2:

• Eingabe: root = [1,3,2,7,6,5,4]
• Ausgabe: 3
• Erklärung:
  • Tauschen Sie 3 und 2. Die 2. Ebene wird zu [2,3].
  • Tausch 7 und 4. Die 3. Ebene wird zu [4,6,5,7].
  • Tauschen Sie 6 und 5. Die 3. Ebene wird zu [4,5,6,7].
  • Wir haben 3 Operationen verwendet, also geben wir 3 zurück.
  • Es kann nachgewiesen werden, dass 3 die Mindestanzahl der erforderlichen Operationen ist.

Beispiel 3:

• Eingabe: root = [1,2,3,4,5,6]
• Ausgabe: 0
• Erklärung: Jede Ebene ist bereits in aufsteigender Reihenfolge sortiert, also geben Sie 0 zurück.

Einschränkungen:

• Die Anzahl der Knoten im Baum liegt im Bereich [1, 10⁵].
• 1 <= Node.val <= 10⁵
• Alle Werte des Baums sind einzigartig.

Hinweis:

1. Wir können die Werte Ebene für Ebene gruppieren und jede Gruppe unabhängig lösen.
2. Führen Sie BFS aus, um den Wert Ebene für Ebene zu gruppieren.
3. Finden Sie die Mindestanzahl an Swaps, um das Array jeder Ebene zu sortieren.
4. Überprüfen Sie beim Durchlaufen des Arrays das aktuelle Element, und wenn es nicht den richtigen Index hat, ersetzen Sie dieses Element durch den Index des Elements, das hätte kommen sollen.

Lösung:

Das Problem besteht darin, die Werte eines Binärbaums Ebene für Ebene in streng aufsteigender Reihenfolge mit der minimalen Anzahl von Operationen zu sortieren. In jeder Operation können wir die Werte zweier Knoten vertauschen, die sich auf derselben Ebene befinden. Das Ziel besteht darin, die Mindestanzahl solcher Operationen zu bestimmen, die erforderlich sind, um die sortierte Reihenfolge zu erreichen.

Kernpunkte:

1. Binärbaumebenen: Auf jeder Ebene des Binärbaums sollten die Werte in streng aufsteigender Reihenfolge sortiert sein.
2. Eindeutige Werte: Alle Knoten haben eindeutige Werte, was die Sortierung erleichtert, da es keine Duplikate gibt.
3. BFS für Ebenengruppierung: Verwenden Sie die Breitensuche (BFS), um den Baum zu durchsuchen und Knoten nach ihren Ebenen zu gruppieren.
4. Minimale Swaps: Für jede Ebene müssen wir die Mindestanzahl an Swaps ermitteln, die erforderlich sind, um die Knotenwerte auf dieser Ebene zu sortieren.
5. Einschränkungen: Der Baum kann bis zu 10^5 Knoten haben, daher muss die Lösung effizient sein.

Ansatz:

1. BFS-Traversal: Führen Sie ein BFS durch, um den Baum zu durchlaufen und die Werte der Knoten auf jeder Ebene zu sammeln.
2. Jede Ebene sortieren: Berechnen Sie für jede Ebene die Mindestanzahl an Swaps, um die Werte in streng aufsteigender Reihenfolge zu sortieren.
3. Zykluszerlegung: Die wichtigste Beobachtung zur Minimierung von Swaps ist, dass das Sortieren eines Arrays als Austausch von Elementen in Zyklen betrachtet werden kann. Die Mindestanzahl an Swaps für jeden Zyklus falsch platzierter Elemente beträgt die Länge des Zyklus minus eins.
4. Akkumulieren von Swaps: Summieren Sie die Swaps für jedes Level, um die Gesamtzahl der erforderlichen Swaps zu erhalten.

Planen:

1. BFS: Durchlaufen Sie den Baum mit BFS, um Knoten auf jeder Ebene zu sammeln.
2. Jede Ebene sortieren: Sortieren Sie die Werte auf jeder Ebene und berechnen Sie die Mindestanzahl an Swaps.
3. Swaps berechnen: Verwenden Sie die Zykluszerlegung, um die minimalen Swaps zu ermitteln, die zum Sortieren der Knoten auf jeder Ebene erforderlich sind.

Lassen Sie uns diese Lösung in PHP implementieren: 2471. Mindestanzahl von Operationen zum Sortieren eines Binärbaums nach Ebene

<?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
     */
}
?>




<h3>
  
  
  Erläuterung:
</h3>

<ol>
<li>
<p><strong>Schritt 1: Führen Sie BFS durch, um Knoten nach Ebene zu gruppieren</strong>:</p>
<ul>
<li>Beginnen Sie an der Wurzel und durchqueren Sie den Baum Ebene für Ebene.</li>
<li>Hängen Sie für jeden Knoten seinen Wert an die entsprechende Ebene im Ebenen-Array an.</li>
</ul>
</li>
<li>
<p><strong>Schritt 2: Berechnen Sie für jede Ebene die minimalen Swaps, um die Werte zu sortieren</strong>:</p>

<ul>
<li>Sortieren Sie die Werte auf jeder Ebene.</li>
<li>Verwenden Sie einen zyklusbasierten Ansatz, um die minimalen Swaps zu berechnen, die erforderlich sind, um die aktuelle Ebene in eine sortierte Ebene umzuwandeln.</li>
</ul>
</li>
<li>
<p><strong>Zykluszerlegung</strong>:</p>

<ul>
<li>Verfolgen Sie für jedes unsortierte Element seinen Zyklus (d. h. wohin es gehen soll) und markieren Sie Elemente als besucht.</li>
<li>Für jeden Zyklus entspricht die Anzahl der erforderlichen Swaps der Länge des Zyklus minus eins.</li>
</ul>
</li>
<li>
<p><strong>Geben Sie die Gesamtzahl der Swaps zurück</strong>:</p>

<ul>
<li>Summieren Sie die für jedes Level erforderlichen Swaps und geben Sie die Summe zurück.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Beispielhafte Vorgehensweise:
</h3>

<h4>
  
  
  Beispiel 1:
</h4>

<p>Eingabebaum:<br>
</p>

<div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false"><?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
     */
}
?>

Nach dem Login kopieren

Stufen:

• Stufe 0: [1]
• Stufe 1: [4, 3]
• Stufe 2: [7, 6, 8, 5]
• Stufe 3: [9, 10]

1. Stufe 1: [4, 3]

   • Sortieren Sie es nach [3, 4] mit 1 Tausch (Tausch 4 und 3).

2. Stufe 2: [7, 6, 8, 5]

   • Sortieren Sie es nach [5, 6, 7, 8] mit 2 Vertauschungen (7 und 5 vertauschen, 8 und 7 vertauschen).

3. Stufe 3: [9, 10]

   • Bereits sortiert, kein Austausch erforderlich.

Gesamt-Swaps = 1 (Level 1) 2 (Level 2) = 3 Swaps.

Ausgabe: 3

Beispiel 2:

Eingabebaum:

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

Stufen:

• Stufe 0: [1]
• Stufe 1: [3, 2]
• Stufe 2: [7, 6, 5, 4]

1. Stufe 1: [3, 2]

   • Sortieren Sie es nach [2, 3] mit 1 Tausch (Tausch 3 und 2).

2. Stufe 2: [7, 6, 5, 4]

   • Sortieren Sie es nach [4, 5, 6, 7] mit 2 Vertauschungen (7 und 4 vertauschen, 6 und 5 vertauschen).

Gesamt-Swaps = 1 (Level 1) 2 (Level 2) = 3 Swaps.

Ausgabe: 3

Zeitkomplexität:

1. BFS: O(N) wobei N die Anzahl der Knoten im Baum ist.
2. Sortieren jeder Ebene: Das Sortieren der Werte auf jeder Ebene erfordert O(L log L), wobei L ist die Anzahl der Knoten auf der aktuellen Ebene. Im schlimmsten Fall beträgt die gesamte Sortierkomplexität O(N log N).
3. Zykluszerlegung: O(L) für jede Ebene.

Daher beträgt die Gesamtzeitkomplexität O(N log N), was angesichts der Einschränkungen effizient genug ist.

Ausgabe zum Beispiel:

Für den Eingabebaum:

<?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
     */
}
?>

Die Ausgabe beträgt 3 Swaps, wie im Beispiel beschrieben.

Diese Lösung berechnet effizient die Mindestanzahl von Swaps, die zum Sortieren jeder Ebene des Binärbaums erforderlich sind, indem BFS verwendet wird, um Knoten nach Ebene zu gruppieren und die Zerlegung zu durchlaufen, um die Anzahl der Swaps zu minimieren. Die zeitliche Komplexität von O(N log N) ist optimal für den Umgang mit Bäumen mit bis zu 10^5 Knoten.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonMindestanzahl von Operationen zum Sortieren eines Binärbaums nach Ebene. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!