Problème 235 : Ancestre commun le plus bas dans un arbre binaire de recherche

Approche : En exploitant la structure ordonnée des arbres binaires de recherche, nous déterminons l'ancestre commun en comparant la valeur du nœud courant avec les valeurs cibles. Si la valeur courante est supérieure aux deux cibles, nous explorons le sous-arbre gauche ; si elle est inférieure aux deux, nous explorons le sous-arbre droit. Dès que la valeur courante se situe dans l'intervalle des cibles (ou correspond à l'une d'entre elles), nous avons trouvé l'ancestre commun le plus bas.

/* Définition d'un nœud d'arbre binaire */
struct NoeudArbre {
    int donnee;
    NoeudArbre* enfantGauche;
    NoeudArbre* enfantDroit;
    NoeudArbre(int x) : donnee(x), enfantGauche(nullptr), enfantDroit(nullptr) {}
};

class Solution {
public:
    NoeudArbre* chercherAncestre(NoeudArbre* sommet, NoeudArbre* noeudA, NoeudArbre* noeudB) {
        if (!sommet) return nullptr;
        if (sommet->donnee > noeudA->donnee && sommet->donnee > noeudB->donnee) {
            return chercherAncestre(sommet->enfantGauche, noeudA, noeudB);
        }
        if (sommet->donnee < noeudA->donnee && sommet->donnee < noeudB->donnee) {
            return chercherAncestre(sommet->enfantDroit, noeudA, noeudB);
        }
        return sommet;
    }
};

Version itérative avec une boucle :

class Solution {
public:
    NoeudArbre* chercherAncestreIteratif(NoeudArbre* sommet, NoeudArbre* noeudA, NoeudArbre* noeudB) {
        while (sommet) {
            if (sommet->donnee > noeudA->donnee && sommet->donnee > noeudB->donnee) {
                sommet = sommet->enfantGauche;
            } else if (sommet->donnee < noeudA->donnee && sommet->donnee < noeudB->donnee) {
                sommet = sommet->enfantDroit;
            } else {
                return sommet;
            }
        }
        return nullptr;
    }
};

Problème 701 : Insertion dans un arbre binaire de recherche

Approche : Pour insérer une valeur, nous parcourons l'arbre en suivant la logique ordonnée : si la valeur est inférieure à celle du nœud courant, nous allons vers le sous-arbre gauche ; si elle est supérieure, vers le sous-arbre droit. Lorsqu'une position nulle est attiente, nous créons un nouveau nœud pour y placer la valeur.

struct NoeudArbre {
    int donnee;
    NoeudArbre* enfantGauche;
    NoeudArbre* enfantDroit;
    NoeudArbre() : donnee(0), enfantGauche(nullptr), enfantDroit(nullptr) {}
    NoeudArbre(int x) : donnee(x), enfantGauche(nullptr), enfantDroit(nullptr) {}
    NoeudArbre(int x, NoeudArbre* g, NoeudArbre* d) : donnee(x), enfantGauche(g), enfantDroit(d) {}
};

class Solution {
public:
    NoeudArbre* insererValeur(NoeudArbre* racine, int nouvelleValeur) {
        if (!racine) {
            return new NoeudArbre(nouvelleValeur);
        }
        if (racine->donnee > nouvelleValeur) {
            racine->enfantGauche = insererValeur(racine->enfantGauche, nouvelleValeur);
        } else {
            racine->enfantDroit = insererValeur(racine->enfantDroit, nouvelleValeur);
        }
        return racine;
    }
};

Problème 450 : Suppression d'un nœud dans un arbre binaire de recherche

Approche : La suppression nécessite une gestion spéciale selon le nombre d'enfants du nœud cible. Si le nœud est une feuille, nous le supprimons directement. S'il a un seul enfant, nous le remplaçons par cet enfant. S'il a deux enfants, nous localisons son successeur in-order (le nœud le plus à gauche dans le sous-arbre droit), puis nous rattachons le sous-arbre gauche du nœud supprimé à ce successeur pour maintenir la structure.

struct NoeudArbre {
    int donnee;
    NoeudArbre* enfantGauche;
    NoeudArbre* enfantDroit;
    NoeudArbre() : donnee(0), enfantGauche(nullptr), enfantDroit(nullptr) {}
    NoeudArbre(int x) : donnee(x), enfantGauche(nullptr), enfantDroit(nullptr) {}
    NoeudArbre(int x, NoeudArbre* g, NoeudArbre* d) : donnee(x), enfantGauche(g), enfantDroit(d) {}
};

class Solution {
public:
    NoeudArbre* retirerNoeud(NoeudArbre* racine, int valeurCible) {
        if (!racine) return nullptr;
        if (racine->donnee == valeurCible) {
            if (!racine->enfantGauche && !racine->enfantDroit) {
                delete racine;
                return nullptr;
            }
            if (!racine->enfantGauche && racine->enfantDroit) {
                NoeudArbre* temp = racine->enfantDroit;
                delete racine;
                return temp;
            }
            if (racine->enfantGauche && !racine->enfantDroit) {
                NoeudArbre* temp = racine->enfantGauche;
                delete racine;
                return temp;
            }
            // Cas avec deux enfants : trouver le successeur in-order
            NoeudArbre* successeur = racine->enfantDroit;
            while (successeur->enfantGauche) {
                successeur = successeur->enfantGauche;
            }
            successeur->enfantGauche = racine->enfantGauche;
            NoeudArbre* aEffacer = racine;
            racine = racine->enfantDroit;
            delete aEffacer;
            return racine;
        }
        if (racine->donnee > valeurCible) {
            racine->enfantGauche = retirerNoeud(racine->enfantGauche, valeurCible);
        } else {
            racine->enfantDroit = retirerNoeud(racine->enfantDroit, valeurCible);
        }
        return racine;
    }
};