So berechnen Sie die Steigung eines Binärbaums in PHP

Die Steigung eines Knotens eines Baums ist der absolute Wert der Differenz zwischen der Summe der Knoten des linken Teilbaums und der Summe der Knoten des rechten Teilbaums des Knotens. Heute werden wir über die Methode zur Berechnung der Steigung eines Binärbaums sprechen. Sie können bei Bedarf darauf zurückgreifen.

Berechnen Sie bei einem gegebenen Binärbaum die Steigung des gesamten Baums.

Die Steigung eines Baumknotens ist definiert als der absolute Wert der Differenz zwischen der Summe der Knoten des linken Teilbaums und der Summe der Knoten des rechten Teilbaums des Knotens. Die Steigung eines leeren Knotens ist 0.

Die Steigung des gesamten Baums ist die Summe der Steigungen aller seiner Knoten.

Beispiel:

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

Ideen zur Problemlösung

Durchlaufen Sie rekursiv den Binärbaum, akkumulieren Sie den Wert von abs($left - $right) und geben Sie jedes Mal die Summe der linken und rechten Knoten sowie den aktuellen Knoten zurück für die nächste Steigungsberechnung.

php-Code

/** 
* 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;
    }
}

Empfohlenes Lernen: php-Video-Tutorial

Das obige ist der detaillierte Inhalt vonSo berechnen Sie die Steigung eines Binärbaums in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!