. Finden Sie den größten Wert in jeder Baumzeile

515. Finden Sie den größten Wert in jeder Baumzeile

Schwierigkeit:Mittel

Themen: Baum, Tiefensuche, Breitensuche, Binärbaum

Gibt bei gegebener Wurzel eines Binärbaums ein Array mit dem größten Wert in jeder Zeile des Baums zurück (0-indiziert).

Beispiel 1:

• Eingabe: root = [1,3,2,5,3,null,9]
• Ausgabe: [1,3,9]

Beispiel 2:

• Eingabe: root = [1,2,3]
• Ausgabe: [1,3]

Einschränkungen:

• Die Anzahl der Knoten im Baum liegt im Bereich [0, 10⁴].
• -2³¹ <= Node.val <= 2³¹ - 1

Lösung:

Das Problem „Finden Sie den größten Wert in jeder Baumzeile“ erfordert die Identifizierung des größten Werts, der auf jeder Ebene (Zeile) eines Binärbaums vorhanden ist. Bei einem gegebenen Binärbaum besteht das Ziel darin, den Baum Zeile für Zeile zu durchlaufen und den Maximalwert aus jeder Zeile zu sammeln. Dieses Problem beinhaltet grundlegende Baumdurchquerungstechniken wie Breadth-First Search (BFS) oder Depth-First Search (DFS).

Wichtige Punkte

1. Baumdurchquerung: Die Lösung besteht darin, alle Ebenen des Binärbaums zu durchlaufen, um den größten Wert auf jeder Ebene zu identifizieren.
2. Breadth-First Search (BFS): BFS eignet sich für den Level-für-Level-Durchlauf, was das Finden des größten Werts in jeder Zeile vereinfacht.
3. Einschränkungen: Behandeln Sie Randfälle wie einen leeren Baum und Knoten mit großen oder kleinen ganzzahligen Werten innerhalb des Einschränkungsbereichs.

Anfahrt

Der einfachste Ansatz zum Ermitteln des größten Werts in jeder Zeile ist die Verwendung von BFS:

• Durchquere den Baum Ebene für Ebene.
• Behalten Sie für jede Ebene den größten Wert im Auge.

Alternativ kann auch DFS verwendet werden:

• Durchqueren Sie den Baum rekursiv und führen Sie eine Aufzeichnung des Maximalwerts in jeder Tiefe.

Planen

1. Initialisieren Sie ein Array, um die größten Werte jeder Zeile zu speichern.
2. Verwenden Sie eine Warteschlange für die BFS-Durchquerung:
   • Beginnen Sie mit dem Wurzelknoten.
   • Verarbeiten Sie alle Knoten auf der aktuellen Ebene, bevor Sie mit der nächsten fortfahren.
3. Für jedes Level:
   • Durchlaufen Sie alle Knoten und ermitteln Sie den Maximalwert.
   • Fügen Sie diesen Wert zum Ergebnisarray hinzu.
4. Gibt das Ergebnisarray nach Abschluss der Durchquerung zurück.

Lösungsschritte

1. Eingabe prüfen: Wenn die Wurzel null ist, wird ein leeres Array zurückgegeben.
2. BFS einrichten:
   • Verwenden Sie eine Warteschlange, die mit dem Stammknoten initialisiert wurde.
   • Initialisieren Sie ein leeres Ergebnisarray.
3. Traverse-Ebenen:
   • Verfolgen Sie für jedes Level den Maximalwert.
   • Untergeordnete Knoten zur Warteschlange für die nächste Ebene hinzufügen.
4. Ergebnisse aktualisieren:
   • Hängen Sie den Maximalwert jeder Ebene an das Ergebnisarray an.
5. Ergebnisse zurückgeben: Gibt das Ergebnisarray zurück, das die größten Werte für jede Zeile enthält.

Lassen Sie uns diese Lösung in PHP implementieren: 515. Finden Sie den größten Wert in jeder Baumzeile

val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

/**
 * @param TreeNode $root
 * @return Integer[]
 */
function largestValues($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$root = new TreeNode(1);
$root->left = new TreeNode(3);
$root->right = new TreeNode(2);
$root->left->left = new TreeNode(5);
$root->left->right = new TreeNode(3);
$root->right->right = new TreeNode(9);

print_r(largestValues($root)); // Output: [1, 3, 9]
?>





  
  
  Erläuterung:



  
  
  Eingabe: [1,3,2,5,3,null,9]




Stufe 0: Knotenwerte: [1] → Maximum: 1.

Ebene 1: Knotenwerte: [3, 2] → Maximum: 3.

Ebene 2: Knotenwerte: [5, 3, 9] → Maximum: 9.
#### Ausgabe: [1, 3, 9].



  
  
  Zeitkomplexität




BFS Traversal: Jeder Knoten wird einmal verarbeitet → O(n).

Maximum finden: Wird während der Durchquerung durchgeführt → O(1) pro Ebene.

Gesamt: O(n).



  
  
  Weltraumkomplexität




Warteschlangenspeicher: Höchstens die Breite des Baums (Anzahl der Knoten auf der größten Ebene) → O(w) wobei w die maximale Breite des Baums ist.



  
  
  Ausgabe als Beispiel


Eingabe: root = [1,3,2,5,3,null,9]


Ausgabe: [1, 3, 9].

Diese BFS-basierte Lösung berechnet effizient den größten Wert in jeder Baumzeile mit linearer Zeitkomplexität. Es behandelt große Bäume, negative Werte und Randfälle effektiv wie leere Bäume.

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 von. Finden Sie den größten Wert in jeder Baumzeile. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!