Finden Sie den Mindestdurchmesser nach dem Zusammenführen zweier Bäume

3203. Finden Sie den Mindestdurchmesser nach dem Zusammenführen zweier Bäume

Schwierigkeit:Schwer

Themen: Baum, Tiefensuche, Breitensuche, Diagramm

Es gibt zwei ungerichtete Bäume mit n und m Knoten, nummeriert von 0 bis n - 1 bzw. von 0 bis m - 1. Sie erhalten zwei 2D-Integer-Arrays „Kanten1“ und „Kanten2“ mit den Längen n – 1 bzw. m – 1, wobei „Kanten1[i] = [a_i, b_i]“ darauf hinweist ist eine Kante zwischen den Knoten a_i und b_i im ersten Baum und Kanten2[i] = [u_i, v_i] zeigt an, dass es eine Kante zwischen den Knoten u_i und v_i im zweiten Baum gibt.

Sie müssen einen Knoten aus dem ersten Baum mit einem anderen Knoten aus dem zweiten Baum über eine Kante verbinden.

Gib den minimalstenmöglichen Durchmesser des resultierenden Baums zurück.

Der Durchmesser eines Baumes ist die Länge des längsten Pfades zwischen zwei beliebigen Knoten im Baum.

Beispiel 1:

• Eingabe: Kanten1 = [[0,1],[0,2],[0,3]], Kanten2 = [[0,1]]
• Ausgabe: 3
• Erklärung: Wir können einen Baum mit einem Durchmesser von 3 erhalten, indem wir Knoten 0 des ersten Baums mit einem beliebigen Knoten des zweiten Baums verbinden.

Beispiel 2:

• Eingabe: Kanten1 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2, 7]], Kanten2 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]]
• Ausgabe: 5
• Erklärung: Wir können einen Baum mit einem Durchmesser von 5 erhalten, indem wir Knoten 0 des ersten Baums mit Knoten 0 des zweiten Baums verbinden.

Einschränkungen:

• 1 5
• edges1.length == n - 1
• edges2.length == m - 1
• Kanten1[i].länge == Kanten2[i].länge == 2
• Kanten1[i] = [a_i, b_i]
• 0 i, b_i
• Kanten2[i] = [u_i, v_i]
• 0 i, v_i
• Die Eingabe wird so generiert, dass Kanten1 und Kanten2 gültige Bäume darstellen.

Hinweis:

1. Angenommen, wir haben Knoten a in Baum1 mit Knoten b in Baum2 verbunden. Die Durchmesserlänge des resultierenden Baums ist der größte der folgenden drei Werte:
   1. Der Durchmesser von Baum 1.
   2. Der Durchmesser von Baum 2.
   3. Die Länge des längsten Pfads, der bei Knoten a beginnt und vollständig innerhalb von Baum 1 liegt. Die Länge des längsten Pfads, der bei Knoten b beginnt und vollständig innerhalb von Baum 2 liegt 1.
   4. Der hinzugefügte Wert im dritten Wert ist auf die zusätzliche Kante zurückzuführen, die wir zwischen den Bäumen 1 und 2 hinzugefügt haben.
2. Die Werte 1 und 2 sind unabhängig von unserer Wahl von a und b konstant. Daher müssen wir a und b so auswählen, dass der Wert 3 minimiert wird.
3. Wenn wir a und b optimal auswählen, haben sie jeweils die Durchmesser von Baum 1 und Baum 2. Welche Knoten des Durchmessers sollten wir genau auswählen?
4. a ist der Mittelpunkt des Durchmessers von Baum 1 und b ist der Mittelpunkt des Durchmessers von Baum 2.

Lösung:

Wir müssen Schritt für Schritt vorgehen und uns dabei darauf konzentrieren, zu verstehen, wie der Durchmesser eines Baumes berechnet wird und wie sich die Verbindung der beiden Bäume auf den Gesamtdurchmesser auswirkt.

Lösungsschritte:

1. Ermitteln Sie den Durchmesser jedes Baumes:

   • Der Durchmesser eines Baumes ist der längste Weg zwischen zwei beliebigen Knoten. Um es zu finden, können wir den folgenden zweistufigen Prozess verwenden:
     1. Führen Sie ein BFS (oder DFS) von einem beliebigen Knoten aus durch, um den am weitesten entfernten Knoten zu finden (nennen wir diesen Knoten A).
     2. Führen Sie ein weiteres BFS (oder DFS) beginnend bei A durch, um den am weitesten von A entfernten Knoten zu finden (nennen wir diesen Knoten B), und der Abstand von A nach B entspricht dem Durchmesser des Baums.

2. Bestimmen Sie die optimalen Knoten zum Verbinden:

   • Aus dem Hinweis in der Aufgabe geht hervor, dass der beste Weg, den zusätzlichen Durchmesser beim Verbinden zweier Bäume zu minimieren, darin besteht, die Mittelpunkte der Durchmesser beider Bäume zu verbinden. Dadurch wird der längste Weg minimiert, der durch die neue Kante verursacht wird.
   • Der optimale Knoten im Durchmesser eines Baumes ist normalerweise die „Mitte“, die gefunden werden kann, indem eine BFS von den Endpunkten des Durchmessers aus durchgeführt und die Mitte des längsten Pfads ermittelt wird.

3. Gesamtdurchmesser minimieren:

   • Sobald wir die Mittelpunkte beider Bäume gefunden haben, ist der neue Durchmesser das Maximum von:
     • Der Durchmesser von Baum 1.
     • Der Durchmesser von Baum 2.
     • Die Summe aus dem längsten Pfad in Baum 1, dem längsten Pfad in Baum 2 und 1 für die neue Verbindungskante.

Lassen Sie uns diese Lösung in PHP implementieren: 3203. Finden Sie den Mindestdurchmesser nach dem Zusammenführen zweier Bäume

<?php /**
 * @param Integer[][] $edges1
 * @param Integer[][] $edges2
 * @return Integer
 */
function minimumDiameterAfterMerge($edges1, $edges2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to find the diameter of a tree and the farthest node from a start node
 *
 * @param $n
 * @param $edges
 * @param $start
 * @return array
 */
function bfs($n, $edges, $start) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to find the diameter of a tree and its center
 *
 * @param $n
 * @param $edges
 * @return array
 */
function getDiameterAndCenter($n, $edges) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$edges1 = [[0,1],[0,2],[0,3]];
$edges2 = [[0,1]];
echo minimumDiameterAfterMerge($edges1, $edges2);  // Output: 3

// Example 2
$edges1 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]];
$edges2 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]];
echo minimumDiameterAfterMerge($edges1, $edges2);  // Output: 5
?>

Erläuterung:

1. BFS-Hilfsfunktion: Die BFS-Funktion berechnet den am weitesten von einem bestimmten Startknoten entfernten Knoten und gibt das Distanzarray und den am weitesten entfernten gefundenen Knoten zurück. Dies ist wichtig für die Berechnung des Baumdurchmessers.

2. Durchmesser und Mittelpunkt abrufen: Die Funktion getDiameterAndCenter ermittelt den Durchmesser eines Baums und seinen Mittelpunkt. Die Mitte des Baumes ist entscheidend für die Minimierung des Durchmessers des neuen Baumes beim Zusammenführen zweier Bäume.

3. Hauptlösung:

   • Wir erstellen zunächst Adjazenzlisten für beide Bäume.
   • Wir berechnen den Durchmesser und die Mitte für beide Bäume.
   • Wir führen BFS von den Zentren beider Bäume aus durch, um die längsten Pfade innerhalb jedes Baums zu erhalten.
   • Zuletzt berechnen wir das Maximum der drei Werte, um den minimalen Durchmesser des zusammengeführten Baums zu erhalten.

Zeitkomplexität:

• Erstellen der Adjazenzliste: O(n m)
• BFS-Durchquerung: O(n m)
• Die Gesamtzeitkomplexität beträgt O(n m), was für die Eingabegrößenbeschränkung von 10⁵ effizient ist.

Dieser Ansatz stellt sicher, dass wir beim Zusammenführen der beiden Bäume den minimal möglichen Durchmesser finden.

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 vonFinden Sie den Mindestdurchmesser nach dem Zusammenführen zweier Bäume. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!