Équilibrer un arbre de recherche binaire

1382. Équilibrer un arbre de recherche binaire

Moyen

Étant donné la racine d'un arbre de recherche binaire, renvoie un arbre de recherche binaire équilibré avec les mêmes valeurs de nœuds. S'il y a plus d'une réponse, renvoyez n'importe laquelle d'entre elles.

Un arbre de recherche binaire est équilibré si la profondeur des deux sous-arbres de chaque nœud ne diffère jamais de plus de 1.

Exemple 1 :

• Entrée : racine = [1,null,2,null,3,null,4,null,null]
• Sortie : [2,1,3,null,null,null,4]
• Explication : Ce n'est pas la seule bonne réponse, [3,1,4,null,2] est également correcte.

Exemple 2 :

• Entrée : racine = [2,1,3]
• Sortie : [2,1,3]

Contraintes :

• Le nombre de nœuds dans l'arborescence est compris entre [1, 10⁴].
• 1 <= Node.val <= 10⁵

Solution :

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @return TreeNode
     */
    function balanceBST($root) {
        $nums = [];
        $this->inorder($root, $nums);
        return $this->build($nums, 0, count($nums) - 1);
    }

    function inorder($root, &$nums) {
        if ($root == null)
        return;
        $this->inorder($root->left, $nums);
        $nums[] = $root->val;
        $this->inorder($root->right, $nums);
    }

    function build($nums, $l, $r) {
        if ($l > $r)
        return null;
        $m = (int)(($l + $r) / 2);
        return new TreeNode($nums[$m], $this->build($nums, $l, $m - 1), $this->build($nums, $m + 1, $r));
    }
}




Liens de contact


LinkedIn
GitHub



          

            
  

            
        
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!