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.

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

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

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.

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:

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!