Höhe des Binärbaums nach Abfragen zum Entfernen von Teilbäumen

2458. Höhe des Binärbaums nach Abfragen zum Entfernen des Teilbaums

Schwierigkeit:Schwer

Themen: Array, Baum, Tiefensuche, Breitensuche, Binärbaum

Sie erhalten die Wurzel eines Binärbaums mit n Knoten. Jedem Knoten wird ein eindeutiger Wert von 1 bis n zugewiesen. Sie erhalten außerdem ein Array-Abfragen der Größe m.

Sie müssen m unabhängige Abfragen für den Baum ausführen, wobei Sie in der i^ten Abfrage Folgendes tun:

• Entfernen den Teilbaum, der am Knoten mit dem Wert query[i] verwurzelt ist, aus dem Baum. Es ist garantiert, dass Abfragen[i] nicht dem Wert der Wurzel entsprechen.

Gib eine Array-Antwort der Größe m zurück, wobei Antwort[i] die Höhe des Baums nach Durchführung der i^tenAbfrage ist.

Hinweis:

• Die Abfragen sind unabhängig, sodass der Baum nach jeder Abfrage in seinen Ausgangszustand zurückkehrt.
• Die Höhe eines Baums ist die Anzahl der Kanten im längsten einfachen Pfad von der Wurzel bis zu einem Knoten im Baum.

Beispiel 1:

• Eingabe: root = [1,3,4,2,null,6,5,null,null,null,null,null,7], Abfragen = [4]
• Ausgabe: [2]
• Erklärung: Das obige Diagramm zeigt den Baum nach dem Entfernen des Teilbaums, der am Knoten mit dem Wert 4 verwurzelt ist.
  • Die Höhe des Baumes beträgt 2 (Der Pfad 1 -> 3 -> 2).

Beispiel 2:

• Eingabe: root = [5,8,9,2,1,3,7,4,6], Abfragen = [3,2,4,8]
• Ausgabe: [3,2,3,2]
• Erklärung: Wir haben die folgenden Fragen:
  • Entfernen des Teilbaums, der am Knoten mit dem Wert 3 verwurzelt ist. Die Höhe des Baums wird 3 (der Pfad 5 -> 8 -> 2 -> 4).
  • Entfernen des Teilbaums, der am Knoten mit dem Wert 2 verwurzelt ist. Die Höhe des Baums wird 2 (der Pfad 5 -> 8 -> 1).
  • Entfernen des Teilbaums, der am Knoten mit dem Wert 4 verwurzelt ist. Die Höhe des Baums wird 3 (der Pfad 5 -> 8 -> 2 -> 6).
  • Entfernen des Teilbaums, der am Knoten mit dem Wert 8 verwurzelt ist. Die Höhe des Baums wird 2 (der Pfad 5 -> 9 -> 3).

Einschränkungen:

• Die Anzahl der Knoten im Baum beträgt n.
• 2 <= n <= 10⁵
• 1 <= Node.val <= n
• Alle Werte im Baum sind einzigartig.
• m == query.length
• 1 <= m <= min(n, 10⁴)
• 1 <= Abfragen[i] <= n
• Abfragen[i] != root.val

Hinweis:

1. Versuchen Sie, die Antwort für jeden Knoten von 1 bis n vorab zu berechnen, und beantworten Sie jede Abfrage in O(1).
2. Die Antworten können in einer einzelnen Baumdurchquerung vorberechnet werden, nachdem die Höhe jedes Teilbaums berechnet wurde.

Lösung:

Die Lösung verwendet einen Zwei-Pass-Ansatz:

1. Berechnen Sie die Höhe jedes Knotens im Baum.
2. Bestimmen Sie die maximale Höhe des Baums, nachdem Sie den Teilbaum entfernt haben, der an jedem abgefragten Knoten verwurzelt ist.

Lassen Sie uns diese Lösung in PHP implementieren: 2458. Höhe des Binärbaums nach Abfragen zum Entfernen von Teilbäumen

Code-Aufschlüsselung

1. Klassendefinition und Eigenschaften:

class Solution {

    private $valToMaxHeight = [];
    private $valToHeight = [];

• valToMaxHeight: Dieses Array speichert die maximale Höhe des Baums nach dem Entfernen des Teilbaums jedes Knotens.
• valToHeight: Dieses Array speichert die Höhe des Teilbaums jedes Knotens.

2. Hauptfunktion:

function treeQueries($root, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

• Die Funktion „treeQueries“ übernimmt die Wurzel des Baums und das Abfragearray.
• Zuerst wird die Höhenfunktion aufgerufen, um die Höhe jedes Knotens zu berechnen.
• Dann wird die Funktion dfs (Tiefensuche) aufgerufen, um die maximalen Höhen nach dem Entfernen von Teilbäumen zu berechnen.
• Schließlich wird das Antwortarray mit den Ergebnissen für jede Abfrage gefüllt.

3. Höhenberechnung:

private function height($node) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

• Diese Funktion berechnet die Höhe jedes Knotens rekursiv.
• Wenn der Knoten null ist, gibt er 0 zurück.
• Wenn die Höhe des Knotens bereits berechnet wurde, wird sie aus dem Cache abgerufen (valToHeight).
• Es berechnet die Höhe basierend auf den Höhen seiner linken und rechten untergeordneten Elemente und speichert sie in valToHeight.

4. Tiefensuche nach maximaler Höhe:

private function dfs($node, $depth, $maxHeight) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

• Diese Funktion führt ein DFS durch, um die maximale Höhe des Baums zu berechnen, nachdem der Teilbaum jedes Knotens entfernt wurde.
• Es zeichnet die aktuelle maximale Höhe in valToMaxHeight für den aktuellen Knoten auf.
• Es berechnet die Höhen der linken und rechten Teilbäume und aktualisiert die maximale Höhe entsprechend.
• Es ruft sich rekursiv für die linken und rechten Kinder auf und aktualisiert die Tiefe und maximale Höhe.

Beispiel-Komplettlösung

Lassen Sie uns ein Beispiel Schritt für Schritt durchgehen.

Beispieleingabe:

// Tree Structure
//        1
//       / \
//      3   4
//     /   / \
//    2   6   5
//         \
//          7

$root = [1, 3, 4, 2, null, 6, 5, null, null, null, null, null, 7];
$queries = [4];

Anfängliche Höhenberechnung:

• Die Höhe des Baumes wurzelt bei 1:3
• Die Höhe des Baumes wurzelt bei 3:2
• Die Höhe des Baumes mit Wurzeln bei 4:2 (Höhe der Teilbäume mit Wurzeln bei 6 und 5)
• Die Höhe des Baumes mit der Wurzel 6:1 (nur Knoten 7)
• Die Höhe des Baumes, der bei 2:0 wurzelt (Blattknoten)

Nach der Höhenberechnung würde valToHeight so aussehen:

class Solution {

    private $valToMaxHeight = [];
    private $valToHeight = [];

DFS für Max Heights:

• Für die Wurzel (1) werden die 4 Blätter des Teilbaums entfernt:
  • Linke Höhe: 2 (gewurzelt bei 3)
  • Rechte Höhe: 1 (wurzelnd bei 5)
• Somit beträgt die maximale Höhe nach dem Entfernen von 4 2.

Ergebnisarray nach Abfragen:

• Für die Abfrage 4 wäre das Ergebnis [2].

Endgültige Ausgabe

Das Ergebnis für die bereitgestellte Eingabe ist:

function treeQueries($root, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

Dieser strukturierte Ansatz stellt sicher, dass wir die erforderlichen Höhen effizient berechnen und jede Anfrage nach der ersten Vorverarbeitung in konstanter Zeit beantworten. Die Gesamtkomplexität beträgt O(n m), wobei n die Anzahl der Knoten im Baum und ist m ist die Anzahl der Abfragen.

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 vonHöhe des Binärbaums nach Abfragen zum Entfernen von Teilbäumen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!