K-te größte Summe in einem Binärbaum

2583. K-te größte Summe in einem Binärbaum

Schwierigkeit:Mittel

Themen: Baum, Breitensuche, Sortierung, Binärbaum

Sie erhalten die Wurzel eines Binärbaums und eine positive ganze Zahl k.

Die Ebenensumme im Baum ist die Summe der Werte der Knoten, die sich auf der gleichen Ebene befinden.

Gib die k^te größte Ebenensumme im Baum zurück (nicht unbedingt eindeutig). Wenn der Baum weniger als k Ebenen enthält, geben Sie -1 zurück.

Beachten Sie, dass zwei Knoten auf der gleichen Ebene liegen, wenn sie den gleichen Abstand von der Wurzel haben.

Beispiel 1:

• Eingabe: root = [5,8,9,2,1,3,7,4,6], k = 2
• Ausgabe: 13
• Erklärung: Die Levelsummen sind die folgenden:
  • Stufe 1: 5.
  • Stufe 2: 8 9 = 17.
  • Stufe 3: 2 1 3 7 = 13.
  • Stufe 4: 4 6 = 10.
  • Die zweitgrößte Levelsumme ist 13.

Beispiel 2:

Eingabe:
• root = [1,2,null,3], k = 1
Ausgabe:
• 3
Erklärung:
• Die größte Levelsumme ist 3.

Einschränkungen:

Die Anzahl der Knoten im Baum beträgt n.

• 2 <= n <= 10
5
• 1 <= Node.val <= 10
6
• 1 <= k <= n

Hinweis:

Ermitteln Sie die Summe der Knotenwerte auf jeder Ebene und geben Sie den k-größten Wert zurück.

1. Um die Summe der Werte der Knoten auf jeder Ebene zu ermitteln, können Sie einen DFS- oder BFS-Algorithmus verwenden, um den Baum zu durchlaufen und die Ebene jedes Knotens zu verfolgen.

Lösung:

Wir folgen diesen Schritten:

Level Order Traversal
1. : Wir werden eine Breitensuche (Breadth-First Search, BFS) verwenden, um den Baum Ebene für Ebene zu durchqueren.
Ebenensummen berechnen
2. : Während der BFS-Durchquerung berechnen wir die Summe der Knotenwerte auf jeder Ebene.
Sortieren und finden Sie die k-größte Summe
3. : Nachdem wir die Summen für alle Ebenen berechnet haben, sortieren wir die Summen und rufen den k-größten Wert ab.
Lassen Sie uns diese Lösung in PHP implementieren:

2583. Kth größte Summe in einem Binärbaum

Erläuterung:

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

/**
 * @param TreeNode $root
 * @param Integer $k
 * @return Integer
 */
function kthLargestLevelSum($root, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1:
// Input: root = [5,8,9,2,1,3,7,4,6], k = 2
$root1 = new TreeNode(5);
$root1->left = new TreeNode(8);
$root1->right = new TreeNode(9);
$root1->left->left = new TreeNode(2);
$root1->left->right = new TreeNode(1);
$root1->right->left = new TreeNode(3);
$root1->right->right = new TreeNode(7);
$root1->left->left->left = new TreeNode(4);
$root1->left->left->right = new TreeNode(6);
echo kthLargestLevelSum($root1, 2); // Output: 13

// Example 2:
// Input: root = [1,2,null,3], k = 1
$root2 = new TreeNode(1);
$root2->left = new TreeNode(2);
$root2->left->left = new TreeNode(3);
echo kthLargestLevelSum($root2, 1); // Output: 3
?>





TreeNode-Klasse
: Wir definieren die TreeNode-Klasse, um einen Knoten im Binärbaum darzustellen, wobei jeder Knoten einen Wert (val), ein linkes Kind (left) und ein rechtes Kind hat (rechts).

BFS-Traversal: Die Funktion kthLargestLevelSum verwendet eine Warteschlange, um einen BFS-Traversal durchzuführen. Für jede Ebene summieren wir die Werte der Knoten und speichern das Ergebnis in einem Array ($levelSums).
Ebenensummen sortieren: Nachdem wir den gesamten Baum durchlaufen und die Ebenensummen berechnet haben, sortieren wir die Summen in absteigender Reihenfolge mit rsort. Dies ermöglicht uns den einfachen Zugriff auf die k-größte Summe.
Edge Case Handling: Wenn es weniger als k Ebenen gibt, geben wir -1 zurück.



  
  
  Zeitkomplexität:




BFS-Traversal: O(n), wobei n die Anzahl der Knoten im Baum ist.

Sortierung: O(m log m), wobei m die Anzahl der Ebenen im Baum ist. Da m viel kleiner als n ist, erfolgt die Sortierung relativ schnell.
Gesamtzeitkomplexität: O(n m log m).



  
  
  Raumkomplexität:




Warteschlange: O(n), zum Speichern von Knoten während BFS.

Ebenensummen: O(m), zum Speichern der Summe jeder Ebene.
Gesamtkomplexität des Raums: O(n).


Dieser Ansatz stellt sicher, dass wir den Baum effizient durchlaufen und die richtige kth größte Ebenensumme zurückgeben.

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 vonK-te größte Summe in einem Binärbaum. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!