Cousins ​​​​dans l'arbre binaire II

2641. Cousins ​​​​dans l'arbre binaire II

Difficulté :Moyen

Sujets : Table de hachage, arbre, recherche en profondeur d'abord, recherche en largeur d'abord, arbre binaire

Étant donné la racine d'un arbre binaire, remplacez la valeur de chaque nœud de l'arbre par la somme de toutes les valeurs de ses cousins.

Deux nœuds d'un arbre binaire sont cousins s'ils ont la même profondeur avec des parents différents.

Renvoyer la racine de l'arbre modifié.

Notez que la profondeur d'un nœud est le nombre d'arêtes dans le chemin allant du nœud racine à celui-ci.

Exemple 1 :

• Entrée : racine = [5,4,9,1,10,null,7]
• Sortie : [0,0,0,7,7,null,11]
• Explication : Le schéma ci-dessus montre l'arbre binaire initial et l'arbre binaire après avoir modifié la valeur de chaque nœud.
  • Le nœud de valeur 5 n'a pas de cousins ​​donc sa somme est 0.
  • Le nœud de valeur 4 n'a pas de cousins ​​donc sa somme est 0.
  • Le nœud de valeur 9 n'a pas de cousins ​​donc sa somme est 0.
  • Le nœud de valeur 1 a un cousin de valeur 7 donc sa somme est 7.
  • Le nœud de valeur 10 a un cousin de valeur 7 donc sa somme est 7.
  • Le nœud de valeur 7 a des cousins ​​de valeurs 1 et 10 donc sa somme est 11.

Exemple 2 :

• Entrée : racine = [3,1,2]
• Sortie : [0,0,0]
• Explication : Le schéma ci-dessus montre l'arbre binaire initial et l'arbre binaire après avoir modifié la valeur de chaque nœud.
  • Le nœud de valeur 3 n'a pas de cousins ​​donc sa somme est 0.
  • Le nœud de valeur 1 n'a pas de cousins ​​donc sa somme est 0.
  • Le nœud de valeur 2 n'a pas de cousins ​​donc sa somme est 0.

Contraintes :

• Le nombre de nœuds dans l'arborescence est compris entre [1, 10⁵].
• 1 <= Node.val <= 10⁴

Indice :

1. Utilisez DFS deux fois.
2. Pour la première fois, trouvez la somme des valeurs de tous les niveaux de l'arbre binaire.
3. Pour la deuxième fois, mettez à jour la valeur du nœud avec la somme des valeurs du niveau actuel - les valeurs du nœud frère.

Solution :

La solution utilise deux fois une approche Depth-First Search (DFS) :

1. Premier DFS : Calculez la somme de toutes les valeurs de nœuds à chaque niveau de l'arborescence.
2. Deuxième DFS : Mettez à jour la valeur de chaque nœud avec la somme des valeurs de ses cousins ​​en soustrayant les valeurs de ses frères et sœurs du total pour ce niveau.

Implémentons cette solution en PHP : 2641. Cousins ​​dans l'arbre binaire 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>
  
  
  Répartition du code
</h3>

<h4>
  
  
  1. Méthode replaceValueInTree
</h4>

<ul>
<li>C'est la méthode principale qui initialise le processus.</li>
<li>Il crée un tableau vide, $levelSums, pour contenir la somme des valeurs à chaque niveau.</li>
<li>Il appelle le premier DFS pour remplir $levelSums, puis appelle le deuxième DFS pour remplacer les valeurs dans l'arborescence.</li>
</ul>

<h4>
  
  
  2. Méthode dfs (Premier DFS)
</h4>

<ul>
<li>
<p><strong>Paramètres :</strong></p>

<ul>
<li>
$root : nœud actuel.</li>
<li>
$level : niveau de profondeur actuel de l'arbre.</li>
<li>
&$levelSums : Référence au tableau où les sommes seront stockées.</li>
</ul>


</li>

<li><p><strong>Cas de base :</strong> Si le nœud est nul, retournez.</p></li>

<li><p>Si la somme du niveau actuel n'est pas initialisée (c'est-à-dire que le niveau n'existe pas dans le tableau), initialisez-la à 0.</p></li>

<li><p>Ajoutez la valeur du nœud actuel à la somme de son niveau.</p></li>

<li><p>Appelez récursivement dfs pour les enfants gauche et droit, en incrémentant le niveau de 1.</p></li>

</ul>

<h4>
  
  
  3. Méthode de remplacement (Deuxième DFS)
</h4>

<ul>
<li>
<p><strong>Paramètres :</strong></p>

<ul>
<li>
$root : nœud actuel.</li>
<li>
$level : niveau de profondeur actuel.</li>
<li>
$curr : Nœud actuel dans l'arborescence modifiée.</li>
<li>
$levelSums : Le tableau avec les sommes pour chaque niveau.</li>
</ul>


</li>

<li>

<p>Calculez la somme des valeurs des cousins :</p>

<ul>
<li>Obtenez la somme totale pour le niveau suivant.</li>
<li>Soustrayez les valeurs des enfants (frères et sœurs) du nœud actuel de ce total pour obtenir la somme des cousins.</li>
</ul>


</li>

<li><p>Si l'enfant de gauche existe, créez un nouveau TreeNode avec la somme des cousins ​​et appelez récursivement replace pour celui-ci.</p></li>

<li><p>Si le bon enfant existe, faites de même pour le bon enfant.</p></li>

</ul>

<h3>
  
  
  Exemple de procédure pas à pas
</h3>

<p>Utilisons le premier exemple de l'invite :</p>

<h4>
  
  
  Saisir
</h4>



<pre class="brush:php;toolbar:false">root = [5,4,9,1,10,null,7]

1. Premier DFS (Calculer les sommes de niveaux) :

   • Niveau 0 : 5 → Somme = 5
   • Niveau 1 : 4 9 → Somme = 13
   • Niveau 2 : 1 10 7 → Somme = 18
   • Niveau finalSommes : [5, 13, 18]

2. Deuxième DFS (Remplacer les valeurs) :

   • Au niveau 0 : 5 n'a pas de cousins ​​→ Remplacer par 0.
   • Au niveau 1 :
     • 4 → Cousins ​​= 9 → Remplacer par 9 (du niveau 1 total, pas de frères et sœurs).
     • 9 → Cousins ​​= 4 → Remplacer par 4.
   • Au niveau 2 :
     • 1 → Cousins ​​​​= 10 7 = 17 → Remplacer par 17.
     • 10 → Cousins ​​= 1 7 = 8 → Remplacer par 8.
     • 7 → Cousins ​​​​= 1 10 = 11 → Remplacer par 11.

Sortir

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

Ce remplacement étape par étape basé sur les valeurs cousines aboutit à l'arbre modifié comme indiqué dans l'exemple.

Résumé

• La solution utilise deux parcours DFS : un pour calculer les sommes et l'autre pour remplacer les valeurs des nœuds.
• La logique garantit que chaque nœud est mis à jour en fonction des valeurs de ses nœuds cousins ​​tout en conservant la structure de l'arbre binaire.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!