Français
Français
Un arbre binaire est une structure de données commune composée de nœuds, où chaque nœud a au plus deux nœuds enfants. Habituellement, la valeur du nœud enfant gauche est inférieure à la valeur du nœud enfant droit. Les arbres binaires sont largement utilisés en informatique, comme la recherche d'arbres binaires, les arbres binaires équilibrés et les tas. Cet article expliquera comment calculer la pente d'un arbre binaire par PHP.
La pente de l'arbre binaire fait référence à la valeur absolue de la différence entre la somme des valeurs de nœud du sous-arbre gauche et du sous-arbre droit de chaque nœud. La pente de l'arbre binaire est la somme des pentes de tous les nœuds.
/**
* Définition du nœud d'arbre binaire
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution {
public $res = 0;
function findTilt($root) {
$this->dfs($root);
return $this->res;
}
// Recherche en profondeur avant pour calculer la pente de l'arbre binaire
function dfs($root) {
if ($root == null) return 0;
$left = $this->dfs($root->left);
$right = $this->dfs($root->right);
$this->res += abs($left - $right);
return $left + $right + $root->val;
}
}
Le code PHP ci-dessus implémente une classe d'arborescence binaire et traverse les nœuds via la recherche en profondeur DFS pour calculer la pente de chaque nœud. La fonction Fintilt est utilisée pour retourner la somme des pentes de l'ensemble de l'arbre binaire. La fonction DFS traverse récursivement chaque nœud et renvoie la somme du sous-arbre gauche et du sous-arbre droit du nœud actuel.
Le processus de calcul de la pente de l'arbre binaire nécessite de traverser tous les nœuds et de calculer la valeur absolue de la différence entre les sous-arbres gauche et droit de chaque nœud. Pendant le processus de traversée, la valeur de la pente de chaque nœud est accumulée et la pente de l'ensemble de l'arbre binaire est finalement obtenue.
Pour atteindre ce calcul, nous utilisons une méthode récursive pour traverser l'arbre binaire de bas en haut. Pour chaque nœud, les pentes de ses sous-arbres gauche et droite sont d'abord calculées, puis la valeur absolue de sa différence est ajoutée à la pente totale.
La complexité du temps est O (n), où n est le nombre de nœuds dans l'arbre binaire.
Cet article décrit comment calculer la pente d'un arbre binaire par PHP. À l'aide de l'algorithme de recherche en profondeur d'abord, nous traversons récursivement chaque nœud, calculons la pente du nœud et l'accumuons, et nous obtenons enfin la pente de l'arborescence entière. L'algorithme a une complexité temporelle d'O (n), qui est une méthode efficace pour faire face au problème de la pente arborescente binaire.
