Comment calculer la pente d'un arbre binaire en PHP

La pente d'un nœud d'un arbre est la valeur absolue de la différence entre la somme des nœuds du sous-arbre gauche et la somme des nœuds du sous-arbre droit du nœud. Aujourd'hui, nous allons parler de la méthode de calcul de la pente d'un arbre binaire. Vous pouvez vous y référer si vous en avez besoin.

Étant donné un arbre binaire, calculez la pente de l'arbre entier.

La pente d'un nœud d'arbre est définie comme la valeur absolue de la différence entre la somme des nœuds du sous-arbre gauche et la somme des nœuds du sous-arbre droit du nœud. La pente d'un nœud vide est 0.

La pente de l'arbre entier est la somme des pentes de tous ses nœuds.

Exemple :

输入：
         1
       /   \
      2     3
输出：1
解释：
结点 2 的坡度: 0
结点 3 的坡度: 0
结点 1 的坡度: |2-3| = 1
树的坡度 : 0 + 0 + 1 = 1

Idées pour résoudre des problèmes

Parcourez de manière récursive l'arbre binaire, accumulez la valeur de abs($left - $right) et renvoyez à chaque fois la somme des nœuds gauche et droit et du nœud actuel pour le prochain calcul de pente.

code php

/** 
* Definition for a binary tree node. 
* class TreeNode { 
* public $val = null; 
* public $left = null; 
* public $right = null; 
* function __construct($value) { 
    $this->val = $value; 
    } 
 * } 
 */
class Solution {

    /** * @param TreeNode $root * @return Integer */
    private $total = 0;
    function findTilt($root) {
        $this->traverse($root);

        return $this->total;
    }

    function  traverse($root) {
        if($root == null) {
            return 0;
        }
    
        $left = $this->traverse($root->left);
        $right = $this->traverse($root->right);
        $this->total += abs($left - $right);

        return $left + $right + $root->val;
    }
}

Apprentissage recommandé : Tutoriel vidéo php

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!