So ermitteln Sie, ob es sich in PHP um einen ausgeglichenen Binärbaum handelt

In Binärbäumen gibt es einen sogenannten ausgeglichenen Binärbaum. Heute stellen wir die Methode zur Beurteilung vor, ob der Baum ein ausgeglichener Binärbaum ist. Freunde in Not können sich darauf beziehen.

Bestimmen Sie anhand eines Binärbaums, ob es sich um einen Binärbaum mit Höhenausgleich handelt.

In dieser Frage ist ein höhenbalancierter Binärbaum definiert als: Der Absolutwert des Höhenunterschieds zwischen dem linken und dem rechten Teilbaum jedes Knotens eines Binärbaums überschreitet nicht 1.

Beispiel 1:

给定二叉树 [3,9,20,null,null,15,7]
   3
   / \
  9  20
    /  \
   15   7

gibt true zurück.

Beispiel 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

return false .

Ideen zur Problemlösung

Das Folgende ist die grundlegendste Brute-Force-Lösungsmethode von oben nach unten. Jeder Knoten kann ein Teilbaum sein, daher müssen Sie feststellen, ob es sich um einen ausgeglichenen Binärbaum handelt. Diese Methode führt zu vielen wiederholten Berechnungen und weist eine hohe Zeitkomplexität auf.

Bottom-up-Frühblockierungsmethode: Die Idee besteht darin, eine Vorbestellungsdurchquerung des Binärbaums durchzuführen und die maximale Höhe des Teilbaums von unten nach oben zurückzugeben wird „beschnitten“ und kehrt direkt nach oben zurück.

Top-down-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 Boolean */
    function isBalanced($root) {
        if ($root == null) {
            return true;
        }
        if (abs($this->getHeight($root->left) - $this->getHeight($root->right)) > 1) {
            return false;
        }
        return $this->isBalanced($root->left) && $this->isBalanced($root->right);
    }
    function getHeight($node)
    {
        if($node == NULL)
            return 0;
        return 1 + max($this->getHeight($node->left), $this->getHeight($node->right));
    }}

Bottom-up-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 Boolean */
    function isBalanced($root) {
        return $this->helper($root) >= 0;
    }
    public function helper($root){
        if($root === null){
            return 0;
        }
        $l = $this->helper($root->left);
        $r = $this->helper($root->right);
        if($l === -1 || $r === -1 || abs($l - $r) > 1) return -1;
            return max($l, $r) +1;
    }}

Empfohlenes Lernen: php-Video-Tutorial

Das obige ist der detaillierte Inhalt vonSo ermitteln Sie, ob es sich in PHP um einen ausgeglichenen Binärbaum handelt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!