Maison > développement back-end > Problème PHP > Comment déterminer s'il s'agit d'un arbre binaire équilibré en PHP

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

醉折花枝作酒筹
Libérer: 2023-03-11 11:48:01
avant
2187 Les gens l'ont consulté

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.

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

É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
Copier après la connexion

renvoie vrai .

Exemple 2 :

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

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
Copier après la connexion

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));
    }}
Copier après la connexion

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;
    }}
Copier après la connexion

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!

Étiquettes associées:
php
source:hxd.life
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal