2641. Cousins im Binärbaum II
Schwierigkeit:Mittel
Themen: Hash-Tabelle, Baum, Tiefensuche, Breitensuche, Binärbaum
Ersetzen Sie bei gegebener Wurzel eines Binärbaums den Wert jedes Knotens im Baum durch die Summe aller Werte seiner Cousins.
Zwei Knoten eines Binärbaums sind Cousins, wenn sie die gleiche Tiefe mit unterschiedlichen Eltern haben.
Gib die Wurzel des geänderten Baums zurück.
Beachten Sie, dass die Tiefe eines Knotens die Anzahl der Kanten im Pfad vom Wurzelknoten zu ihm ist.
Beispiel 1:
Beispiel 2:
Einschränkungen:
Hinweis:
Lösung:
Die Lösung verwendet zweimal einen DFS-Ansatz (Depth-First Search):
Lassen Sie uns diese Lösung in PHP implementieren: 2641. Cousins im Binärbaum II
<?php
// Definition for a binary tree node.
class TreeNode {
public $val = null;
public $left = null;
public $right = null;
public function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
class Solution {
/**
* @param TreeNode $root
* @return TreeNode
*/
public function replaceValueInTree($root) {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* DFS to calculate the sum of node values at each level.
* @param $root - current node
* @param $level - current depth level in the tree
* @param $levelSums - array holding the sum of values at each level
* @return void
*/
private function dfs($root, $level, &$levelSums) {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* DFS to replace the node values with the sum of cousins' values.
* @param $root - current node in the original tree
* @param $level - current depth level in the tree
* @param $curr - node being modified in the new tree
* @param $levelSums - array holding the sum of values at each level
* @return mixed
*/
private function replace($root, $level, $curr, $levelSums) {
...
...
...
/**
* go to ./solution.php
*/
}
}
// Helper function to print the tree (for testing purpose)
function printTree($root) {
if ($root === null) return [];
$result = [];
$queue = [$root];
while (!empty($queue)) {
$node = array_shift($queue);
if ($node !== null) {
$result[] = $node->val;
$queue[] = $node->left;
$queue[] = $node->right;
} else {
$result[] = null;
}
}
// Remove trailing null values for clean output
while (end($result) === null) {
array_pop($result);
}
return $result;
}
// Example usage:
// Tree: [5,4,9,1,10,null,7]
$root = new TreeNode(5);
$root->left = new TreeNode(4);
$root->right = new TreeNode(9);
$root->left->left = new TreeNode(1);
$root->left->right = new TreeNode(10);
$root->right->right = new TreeNode(7);
$solution = new Solution();
$modifiedTree = $solution->replaceValueInTree($root);
print_r(printTree($modifiedTree)); // Output: [0, 0, 0, 7, 7, null, 11]
?>
<h3>
Aufschlüsselung des Kodex
</h3>
<h4>
1. replaceValueInTree-Methode
</h4>
<ul>
<li>Dies ist die Hauptmethode, die den Prozess initialisiert.</li>
<li>Es wird ein leeres Array, $levelSums, erstellt, um die Summe der Werte auf jeder Ebene zu speichern.</li>
<li>Es ruft das erste DFS auf, um $levelSums zu füllen, und ruft dann das zweite DFS auf, um die Werte im Baum zu ersetzen.</li>
</ul>
<h4>
2. dfs-Methode (erstes DFS)
</h4>
<ul>
<li>
<p><strong>Parameter:</strong></p>
<ul>
<li>
$root: Aktueller Knoten.</li>
<li>
$level: Aktuelle Tiefenebene des Baums.</li>
<li>
&$levelSums: Verweis auf das Array, in dem Summen gespeichert werden.</li>
</ul>
</li>
<li><p><strong>Basisfall:</strong> Wenn der Knoten null ist, kehren Sie zurück.</p></li>
<li><p>Wenn die Summe der aktuellen Ebene nicht initialisiert ist (d. h. die Ebene nicht im Array vorhanden ist), initialisieren Sie sie auf 0.</p></li>
<li><p>Addieren Sie den Wert des aktuellen Knotens zur Summe für seine Ebene.</p></li>
<li><p>Rufen Sie dfs für die linken und rechten Kinder rekursiv auf und erhöhen Sie die Ebene um 1.</p></li>
</ul>
<h4>
3. Methode ersetzen (Zweite DFS)
</h4>
<ul>
<li>
<p><strong>Parameter:</strong></p>
<ul>
<li>
$root: Aktueller Knoten.</li>
<li>
$level: Aktuelles Tiefenniveau.</li>
<li>
$curr: Aktueller Knoten im geänderten Baum.</li>
<li>
$levelSums: Das Array mit Summen für jede Ebene.</li>
</ul>
</li>
<li>
<p>Berechnen Sie die Summe der Cousinswerte:</p>
<ul>
<li>Erhalten Sie die Gesamtsumme für das nächste Level.</li>
<li>Subtrahieren Sie die Werte der Kinder (Geschwister) des aktuellen Knotens von dieser Summe, um die Summe der Cousins zu erhalten.</li>
</ul>
</li>
<li><p>Wenn das linke Kind vorhanden ist, erstellen Sie einen neuen TreeNode mit der Summe der Cousins und rufen Sie rekursiv „replace“ dafür auf.</p></li>
<li><p>Wenn das richtige Kind existiert, machen Sie dasselbe für das richtige Kind.</p></li>
</ul>
<h3>
Beispiel-Komplettlösung
</h3>
<p>Verwenden wir das erste Beispiel aus der Eingabeaufforderung:</p>
<h4>
Eingang
</h4>
<pre class="brush:php;toolbar:false">root = [5,4,9,1,10,null,7]
Erstes DFS (Ebenensummen berechnen):
Zweites DFS (Werte ersetzen):
<?php
// Definition for a binary tree node.
class TreeNode {
public $val = null;
public $left = null;
public $right = null;
public function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
class Solution {
/**
* @param TreeNode $root
* @return TreeNode
*/
public function replaceValueInTree($root) {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* DFS to calculate the sum of node values at each level.
* @param $root - current node
* @param $level - current depth level in the tree
* @param $levelSums - array holding the sum of values at each level
* @return void
*/
private function dfs($root, $level, &$levelSums) {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* DFS to replace the node values with the sum of cousins' values.
* @param $root - current node in the original tree
* @param $level - current depth level in the tree
* @param $curr - node being modified in the new tree
* @param $levelSums - array holding the sum of values at each level
* @return mixed
*/
private function replace($root, $level, $curr, $levelSums) {
...
...
...
/**
* go to ./solution.php
*/
}
}
// Helper function to print the tree (for testing purpose)
function printTree($root) {
if ($root === null) return [];
$result = [];
$queue = [$root];
while (!empty($queue)) {
$node = array_shift($queue);
if ($node !== null) {
$result[] = $node->val;
$queue[] = $node->left;
$queue[] = $node->right;
} else {
$result[] = null;
}
}
// Remove trailing null values for clean output
while (end($result) === null) {
array_pop($result);
}
return $result;
}
// Example usage:
// Tree: [5,4,9,1,10,null,7]
$root = new TreeNode(5);
$root->left = new TreeNode(4);
$root->right = new TreeNode(9);
$root->left->left = new TreeNode(1);
$root->left->right = new TreeNode(10);
$root->right->right = new TreeNode(7);
$solution = new Solution();
$modifiedTree = $solution->replaceValueInTree($root);
print_r(printTree($modifiedTree)); // Output: [0, 0, 0, 7, 7, null, 11]
?>
Diese schrittweise Ersetzung basierend auf Cousin-Werten führt zu dem geänderten Baum, wie im Beispiel gezeigt.
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:
Das obige ist der detaillierte Inhalt vonCousins im Binärbaum II. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
