Nous abordons trois problèmes LeetCode classiques impliquant des arbres binaires, en utilisant des techniques de parcousr en C++. Ces problèmes couvrent la vérification d'équilibre, la génération de tous les chemins et le calcul de la somme des feuilles gauches.

Problème 110 : Arbre binaire équilibré

Pour déterminer si un arbre binaire est équilibré, un parcours postordre est employé. L'approche consiste à calculer les hauteurs des sous-arbres gauche et droit, puis à vérifier leur différence absolue. Si un sous-arbre est déséquilibré, la valeur -1 est propagée aux nœuds parents pour signaler l'erreur. Autrement, la hauteur du nœud actuel est définie comme le maximum des hauteurs des sous-arbres augmenté de un.

class Solution {
public:
    int calculerHauteur(TreeNode* noeud) {
        if (!noeud) return 0;
        int hauteurGauche = calculerHauteur(noeud->left);
        if (hauteurGauche == -1) return -1;
        int hauteurDroite = calculerHauteur(noeud->right);
        if (hauteurDroite == -1) return -1;
        if (abs(hauteurDroite - hauteurGauche) > 1) return -1;
        return 1 + max(hauteurDroite, hauteurGauche);
    }

    bool estEquilibre(TreeNode* racine) {
        return calculerHauteur(racine) != -1;
    }
};

Problème 257 : Tous les chemins de l'arbre binaire

Ce problème requiert un parcours préordre avec backtracking. Les nœuds sont ajoutés à un chemin au fur et à mesure de l'exploration. Lorsqu'une feuille est atteinte, le chemin complet est enregistré sous forme de chaîne. Pour assurer le backtracking, le dernier nœud est retiré après l'exploration de chaque sous-arbre, permettant ainsi de réutiliser le chemin pour d'autres branches.

class Solution {
public:
    vector<string> tousLesChemins;

    void parcourir(TreeNode* noeud, vector<int>& chemin, vector<string>& resultats) {
        chemin.push_back(noeud->val);
        if (!noeud->left && !noeud->right) {
            string cheminStr;
            for (size_t i = 0; i < chemin.size() - 1; ++i) {
                cheminStr += to_string(chemin[i]) + "->";
            }
            cheminStr += to_string(chemin.back());
            resultats.push_back(cheminStr);
            return;
        }
        if (noeud->left) {
            parcourir(noeud->left, chemin, resultats);
            chemin.pop_back();
        }
        if (noeud->right) {
            parcourir(noeud->right, chemin, resultats);
            chemin.pop_back();
        }
    }

    vector<string> cheminsArbreBinaire(TreeNode* racine) {
        vector<int> chemin;
        vector<string> resultats;
        if (!racine) return resultats;
        parcourir(racine, chemin, resultats);
        return resultats;
    }
};
</string></int></string></string></int></string>

Problème 404 : Somme des feuilles gauches

La difficulté réside dans l'identification des feuilles gauches, car on ne peut pas déterminer directement si une feuille est gauche lors de son traitement. Cette vérification doit être effectuée au niveau du nœud parent : si un nœud possède un enfant gauche qui est une feuille, sa valeur est ajoutée à la somme. Ensuite, les sommes des feuilles gauches des sous-arbres gauche et droit sont combinées pour obtenir le résultat final.

class Solution {
public:
    int sommeFeuillesGauches(TreeNode* racine) {
        if (!racine) return 0;
        int somme = 0;
        if (racine->left && !racine->left->left && !racine->left->right) {
            somme += racine->left->val;
        }
        somme += sommeFeuillesGauches(racine->left) + sommeFeuillesGauches(racine->right);
        return somme;
    }
};