- Élaguer un arbre binaire de recherche
Pour résoudre ce problème, on utilise une approche récursive. Si un nœud a une valeur inférieure à la borne basse, il faut explorer son sous-arbre droit et renvoyer le résultat, car les nœuds adéquats s'y trouvent potentiellement. De même, si la valeur dépasse la borne haute, on explore le sous-arbre gauche. Lorsque le nœud est dans l'intervalle, on appliuqe récursivement l'élagage aux sous-arbres gauche et droit.
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def elaguer_arbre(self, noeud: Optional[TreeNode], minimum: int, maximum: int) -> Optional[TreeNode]:
if noeud is None:
return None
if noeud.val < minimum:
# Le nœud est trop petit, on passe au sous-arbre droit
return self.elaguer_arbre(noeud.right, minimum, maximum)
if noeud.val > maximum:
# Le nœud est trop grand, on passe au sous-arbre gauche
return self.elaguer_arbre(noeud.left, minimum, maximum)
# Élagage récursif des sous-arbres
noeud.left = self.elaguer_arbre(noeud.left, minimum, maximum)
noeud.right = self.elaguer_arbre(noeud.right, minimum, maximum)
return noeud
La complexité temporelle est O(n) car chaque nœud est visité une fois. La complexité spatiale est O(h), où h est la hauteur de l'arbre, allant de O(log n) pour un arbre équilibré à O(n) dans le pire cas.
- Convertir un tableau trié en arbre binaire de recherche
Pour obtenir un arbre binaire de recherche équilibré, on procède par recherche binaire récursive. En sélectionnant l'élément médian du tableau comme racine, on garantit que les sous-arbres gauche et droit sont également équilibrés. La récursion s'arrête lorsque l'intervalle devient invalide.
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def construire_abr(self, elements: List[int], debut: int, fin: int) -> Optional[TreeNode]:
if debut > fin:
return None
milieu = debut + (fin - debut) // 2
racine = TreeNode(elements[milieu])
racine.left = self.construire_abr(elements, debut, milieu - 1)
racine.right = self.construire_abr(elements, milieu + 1, fin)
return racine
def tableau_vers_abr(self, elements: List[int]) -> Optional[TreeNode]:
return self.construire_abr(elements, 0, len(elements) - 1)
La complexité temporelle est O(n) pour parcourir tous les éléments. La complexité spaitale est O(log n) due à l'équilibrage de l'arbre, assurant une profondeur logarithmique.
- Transformer un arbre binaire de recherche en arbre cumulatif
Ce problème se résout par un parcours inversé (droite-centre-gauche) de l'arbre binaire de recherche, ce qui équivaut à traiter les valeurs en ordre décroissant. Une variable globale accumule la somme des valeurs visitées, mise à jour à chaque nœud.
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def convertir_en_cumulatif(self, racine: Optional[TreeNode]) -> Optional[TreeNode]:
self.somme_cumulee = 0
self._parcours_inversé(racine)
return racine
def _parcours_inversé(self, noeud: Optional[TreeNode]):
if noeud is None:
return
self._parcours_inversé(noeud.right)
noeud.val += self.somme_cumulee
self.somme_cumulee = noeud.val
self._parcours_inversé(noeud.left)
La complexité temporelle est O(n) pour visiter chaque nœud. La complexité spatiale est O(h), similaire aux cas précédents, dépendant de la forme de l'arbre.