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 :
Exemple 2 :
Contraintes :
Indice :
Solution :
La solution utilise deux fois une approche Depth-First Search (DFS) :
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]
Premier DFS (Calculer les sommes de niveaux) :
Deuxième DFS (Remplacer les valeurs) :
<?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.
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 :
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!
Comment résoudre 400 mauvaises requêtes
Le rôle de c++ce pointeur
Quels sont les algorithmes de cryptage GSM ?
Méthodes de défense contre les attaques du serveur
La différence entre scratch et python
Quels sont les avantages du framework SpringBoot ?
commandes communes postgresql
ps quitter la touche de raccourci plein écran
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
