Cousins ​​im Binärbaum II

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:

• Eingabe: root = [5,4,9,1,10,null,7]
• Ausgabe: [0,0,0,7,7,null,11]
• Erklärung: Das obige Diagramm zeigt den anfänglichen Binärbaum und den Binärbaum nach der Änderung des Werts jedes Knotens.
  • Knoten mit dem Wert 5 hat keine Cousins, daher ist seine Summe 0.
  • Knoten mit dem Wert 4 hat keine Cousins, daher ist seine Summe 0.
  • Knoten mit dem Wert 9 hat keine Cousins, daher ist seine Summe 0.
  • Knoten mit Wert 1 hat einen Cousin mit Wert 7, daher ist seine Summe 7.
  • Knoten mit dem Wert 10 hat einen Cousin mit dem Wert 7, daher ist seine Summe 7.
  • Knoten mit dem Wert 7 hat Cousins ​​mit den Werten 1 und 10, daher ist seine Summe 11.

Beispiel 2:

• Eingabe: root = [3,1,2]
• Ausgabe: [0,0,0]
• Erklärung: Das obige Diagramm zeigt den anfänglichen Binärbaum und den Binärbaum nach der Änderung des Werts jedes Knotens.
  • Knoten mit dem Wert 3 hat keine Cousins, daher ist seine Summe 0.
  • Knoten mit dem Wert 1 hat keine Cousins, daher ist seine Summe 0.
  • Knoten mit dem Wert 2 hat keine Cousins, daher ist seine Summe 0.

Einschränkungen:

• Die Anzahl der Knoten im Baum liegt im Bereich [1, 10⁵].
• 1 <= Node.val <= 10⁴

Hinweis:

1. Verwenden Sie DFS zweimal.
2. Ermitteln Sie zum ersten Mal die Summe der Werte aller Ebenen des Binärbaums.
3. Aktualisieren Sie zum zweiten Mal den Wert des Knotens mit der Summe der Werte der aktuellen Ebene – den Werten des Geschwisterknotens.

Lösung:

Die Lösung verwendet zweimal einen DFS-Ansatz (Depth-First Search):

1. Erstes DFS: Berechnen Sie die Summe aller Knotenwerte auf jeder Ebene des Baums.
2. Zweites DFS: Aktualisieren Sie den Wert jedes Knotens mit der Summe der Werte seiner Cousins, indem Sie die Werte seiner Geschwister von der Summe für diese Ebene subtrahieren.

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]

1. Erstes DFS (Ebenensummen berechnen):

   • Stufe 0: 5 → Summe = 5
   • Stufe 1: 4 9 → Summe = 13
   • Stufe 2: 1 10 7 → Summe = 18
   • AbschlussniveauSummen: [5, 13, 18]

2. Zweites DFS (Werte ersetzen):

   • Auf Level 0: 5 hat keine Cousins ​​→ Durch 0 ersetzen.
   • Auf Stufe 1:
     • 4 → Cousins ​​= 9 → Ersetzen durch 9 (von Level 1 insgesamt, keine Geschwister).
     • 9 → Cousins ​​= 4 → Ersetzen durch 4.
   • Auf Stufe 2:
     • 1 → Cousins ​​= 10 7 = 17 → Ersetzen durch 17.
     • 10 → Cousins ​​= 1 7 = 8 → Ersetzen durch 8.
     • 7 → Cousins ​​= 1 10 = 11 → Ersetzen durch 11.

Ausgabe

<?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.

Zusammenfassung

• Die Lösung verwendet zwei DFS-Durchläufe: einen zum Berechnen der Summen und den anderen zum Ersetzen von Knotenwerten.
• Die Logik stellt sicher, dass jeder Knoten basierend auf den Werten seiner Cousin-Knoten aktualisiert wird, während die Struktur des Binärbaums erhalten bleibt.

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 vonCousins ​​im Binärbaum II. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!