Comment déterminer s'il s'agit d'un arbre binaire équilibré en PHP

Dans les arbres binaires, il en existe un appelé arbre binaire équilibré. Aujourd'hui, nous allons présenter la méthode permettant de juger si l'arbre est un arbre binaire équilibré. Les amis dans le besoin peuvent s'y référer.

Étant donné un arbre binaire, déterminez s'il s'agit d'un arbre binaire équilibré en hauteur.

Dans cette question, un arbre binaire équilibré en hauteur est défini comme : la valeur absolue de la différence de hauteur entre les sous-arbres gauche et droit de chaque nœud d'un arbre binaire ne dépasse pas 1.

Exemple 1 :

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

renvoie vrai .

Exemple 2 :

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

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

return false .

Idées de résolution de problèmes

Ce qui suit est la méthode de solution par force brute la plus basique, de haut en bas. Chaque nœud peut être un sous-arbre, vous devez donc déterminer s'il s'agit d'un arbre binaire équilibré. Cette méthode produira de nombreux calculs répétés et présente une complexité temporelle élevée.

Méthode de blocage précoce ascendante : l'idée est d'effectuer un parcours pré-commandé de l'arbre binaire et de renvoyer la hauteur maximale du sous-arbre de bas en haut. S'il est déterminé qu'un sous-arbre n'est pas un arbre équilibré, il est déterminé. sera "élagué" et renvoyé directement vers le haut.

Code PHP descendant

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

Code PHP ascendant :

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

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!