Différence Absolue Minimale dans un Arbre Binaire de Recherche (LeetCode 530)

Pour résoudre ce problème, nous exploitons la propriété fondamentale des arbres binaires de recherche (ABR) : un parcours infixe (gauche, racine, droite) génère une séquence strictement triée de valeurs. La différence absolue minimale se trouvera donc nécessairement entre deux nœuds consécutifs dans cet ordre de traversal. Plutôt que de stocker tous les éléments, nous pouvons maintenir un pointeur sur le nœud précédemment visité pour calculer la différence à la volée.

class Solution {
private:
    TreeNode* dernierNoeud = nullptr;
    int differenceMinimale = INT_MAX;

    void parcoursInfixe(TreeNode* noeudCourant) {
        if (!noeudCourant) return;

        // Traversée du sous-arbre gauche
        parcoursInfixe(noeudCourant->left);

        // Traitement du nœud courant
        if (dernierNoeud != nullptr) {
            differenceMinimale = min(differenceMinimale, noeudCourant->val - dernierNoeud->val);
        }
        dernierNoeud = noeudCourant;

        // Traversée du sous-arbre droit
        parcoursInfixe(noeudCourant->right);
    }

public:
    int getMinimumDifference(TreeNode* root) {
        dernierNoeud = nullptr;
        differenceMinimale = INT_MAX;
        parcoursInfixe(root);
        return differenceMinimale;
    }
};

Recherche du Mode dans un Arbre Binaire de Recherche (LeetCode 501)

La recherche du mode (la ou les valeurs les plus fréquentes) dans un ABR peut également être optimisée grâce au parcours infixe. Puisque les valeurs identiques sont regroupées dans un ABR, nous pouvons maintenir un compteur de fréquance courant et un compteur de fréquence maximale. Cela nous permet de déterminer les modes en une seule pasce, sans avoir besoin de structures de données supplémentaires comme une table de hachage.

class Solution {
private:
    TreeNode* precedent = nullptr;
    int frequenceCourante = 0;
    int frequenceMaximale = 0;
    vector<int> modes;

    void analyserNoeud(TreeNode* noeud) {
        if (!noeud) return;

        // Traversée gauche
        analyserNoeud(noeud->left);

        // Mise à jour de la fréquence
        if (precedent && precedent->val == noeud->val) {
            frequenceCourante++;
        } else {
            frequenceCourante = 1;
        }
        precedent = noeud;

        // Mise à jour de la liste des modes
        if (frequenceCourante > frequenceMaximale) {
            frequenceMaximale = frequenceCourante;
            modes.clear();
            modes.push_back(noeud->val);
        } else if (frequenceCourante == frequenceMaximale) {
            modes.push_back(noeud->val);
        }

        // Traversée droite
        analyserNoeud(noeud->right);
    }

public:
    vector<int> findMode(TreeNode* root) {
        precedent = nullptr;
        frequenceCourante = 0;
        frequenceMaximale = 0;
        modes.clear();
        analyserNoeud(root);
        return modes;
    }
};

Ancêtre Commun le Plus Bas dans un Arbre Binaire (LeetCode 236)

Contrairement aux ABR, un arbre binaire standard ne possède pas de propriété d'ordre. Pour trouver l'ancêtre commun le plus bas (Lowest Common Ancester) de deux nœuds donnés, nous devons utiliser un parcours post-fixe (gauche, droite, racine). Cette approche bottom-up nous permet de remonter les informations depuis les feuilles vers la racine. Si les sous-arbres gauche et droit retournent tous deux un nœud non nul, cela signifie que le nœud courant est le point de convergence, donc l'ancêtre commun le plus bas.

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // Cas de base : si on trouve p, q, ou si on atteint une feuille
        if (root == nullptr || root == p || root == q) {
            return root;
        }

        // Récursion sur les sous-arbres gauche et droit
        TreeNode* resultatGauche = lowestCommonAncestor(root->left, p, q);
        TreeNode* resultatDroit = lowestCommonAncestor(root->right, p, q);

        // Si les deux côtés retournent un nœud non nul, le nœud courant est le LCA
        if (resultatGauche != nullptr && resultatDroit != nullptr) {
            return root;
        }

        // Sinon, on remonte le résultat non nul (s'il y en a un)
        return (resultatGauche != nullptr) ? resultatGauche : resultatDroit;
    }
};