Deutsch
Deutsch
Ein Binärbaum ist eine gemeinsame Datenstruktur, die aus Knoten besteht, wobei jeder Knoten höchstens zwei untergeordnete Knoten hat. Normalerweise ist der Wert des linken Kinderknotens kleiner als der Wert des rechten Kinderknotens. Binärbäume werden in der Informatik häufig verwendet, wie beispielsweise bei der Suche nach binären Bäumen, in ausgewogenen Bäumen und Haufen. In diesem Artikel wird erläutert, wie die Steigung eines binären Baums durch PHP berechnet wird.
Die Binärbaumsteigung bezieht sich auf den Absolutwert der Differenz zwischen der Summe der Knotenwerte des linken Subtree und dem rechten Teilbaum jedes Knotens. Die Steigung des Binärbaums ist die Summe der Hänge aller Knoten.
/**
* Binärbaumknotendefinition
* 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;
}
// Tiefe-First-Suche zur Berechnung der binären Baumsteigung
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;
}
}
Der obige PHP-Code implementiert eine binäre Baumklasse und führt Knoten durch die DFS-Tiefensuche durch, um die Steigung jedes Knotens zu berechnen. Die Funktion findtilt wird verwendet, um die Summe der Hänge des gesamten Binärbaums zurückzugeben. Die DFS -Funktion durchquert rekursiv jeden Knoten und gibt die Summe des linken Unterbaums und des rechten Teilbaums des aktuellen Knotens zurück.
Der Prozess der Berechnung der Binärbaumsteigung erfordert das Durchqueren aller Knoten und die Berechnung des Absolutwerts der Differenz zwischen den linken und rechten Teilbäumen jedes Knotens. Während des Traversalprozesses wird der Steigungswert jedes Knotens akkumuliert und die Steigung des gesamten Binärbaums schließlich erhalten.
Um diese Berechnung zu erreichen, verwenden wir eine rekursive Methode, um den binären Baum von unten nach oben zu durchqueren. Für jeden Knoten werden zuerst die Steigungen seiner linken und rechten Unterbaume berechnet, und dann wird der absolute Wert seiner Differenz der Gesamtsteigung hinzugefügt.
Die zeitliche Komplexität ist O (n), wobei n die Anzahl der Knoten im binären Baum ist.
In diesem Artikel wird beschrieben, wie die Steigung eines binären Baums durch PHP berechnet wird. Mit dem Tiefen-ersten-Such-Algorithmus durchqueren wir jeden Knoten rekursiv, berechnen die Knotensteigung und sammeln ihn an und erhalten schließlich die Steigung des gesamten Baumes. Der Algorithmus hat eine zeitliche Komplexität von O (n), was eine effiziente Methode ist, um mit dem Problem der Binärbaumneigung zu gelangen.
