Description du Problème

Vous êtes donné la racine d'un arbre binaire et vous devez déterminer s'il s'agit d'un arbre binaire de recherche valide.

Une arbre binaire de recherche (ABR) est défini par les propriétés suivantes :

• Tous les nœuds de son sous-arbre gauche sont inférieurs à la valeur du nœud actuel.
• Tous les nœuds de son sous-arbre droit sont supérieurs à la valeur du nœud actuel.
• Tous les sous-arbres gauche et droit doivent également être des arbres binaires de recherche valides.

Analyse

Cette question peut être résolue par récursion. Il est important de noter que tous les nœuds du sous-arbre gauche doivent être inférieurs au nœud actuel, et non seulement ceux du niveau immédiatement inférieur. Par conséquent, il est nécessaire de transmetttre des limites lors de la récursion pour effectuer des comparaisons appropriées.

Une autre approche consiste à utiliser la propriété selon laquelle le parcours inordre d'un ABR produit une séquence strictement croissante. On peut résoudre ce problème en utilisant une pile ou d'autres méthodes.

Méthode 1 : Récursion

class Solution {
public:
    const long long MIN_VAL = -2e10;
    const long long MAX_VAL = 2e10;
    
    bool checkNode(TreeNode* noeud, long long minBorne, long long maxBorne) {
        if (noeud == nullptr) {
            return true;
        }
        if (noeud->val <= minBorne || noeud->val >= maxBorne) {
            return false;
        }
        return checkNode(noeud->gauche, minBorne, noeud->val) && checkNode(noeud->droit, noeud->val, maxBorne);
    }
    
    bool estValideBST(TreeNode* racine) {
        return checkNode(racine, MIN_VAL, MAX_VAL);
    }
};

Méthode 2 : Utilisation de la propriété du parcours inordre

class Solution {
public:
    vector<int> valeurs;
    
    void parcoursInordre(TreeNode* noeud) {
        if (noeud == nullptr) {
            return;
        }
        parcoursInordre(noeud->gauche);
        valeurs.push_back(noeud->val);
        parcoursInordre(noeud->droit);
    }
    
    bool estValideBST(TreeNode* racine) {
        parcoursInordre(racine);
        for (size_t i = 1; i < valeurs.size(); ++i) {
            if (valeurs[i] <= valeurs[i - 1]) {
                return false;
            }
        }
        return true;
    }
};

Exemple de Code Incorrect

/**
 * Définition pour un nœud d'arbre binaire.
 * struct TreeNode {
 *     int val;
 *     TreeNode *gauche;
 *     TreeNode *droit;
 *     TreeNode() : val(0), gauche(nullptr), droit(nullptr) {}
 *     TreeNode(int x) : val(x), gauche(nullptr), droit(nullptr) {}
 *     TreeNode(int x, TreeNode *gauche, TreeNode *droit) : val(x), gauche(gauche), droit(droit) {}
 * };
 */
class Solution {
private:
    bool explorer(TreeNode* noeud) {
        bool resultat = true;
        if (noeud->gauche) {
            resultat = (noeud->gauche->val < noeud->val);
            resultat = resultat && explorer(noeud->gauche);
        }
        if (noeud->droit) {
            resultat = resultat && (noeud->droit->val > noeud->val);
            resultat = resultat && explorer(noeud->droit);
        }
        return resultat;
    }
public:
    bool estValideBST(TreeNode* racine) {
        return explorer(racine);
    }
};

Erreur Ignorée

La définition d'un ABR stipule que :

• Tous les nœuds du sous-arbre gauche doivent être inférieurs au nœud.
• Tous les nœuds du sous-arbre droit doivent être supéreiurs au nœud.

Il ne suffit pas de vérifier uniquement les nœuds directs. Par exemple :

    5
   / \
  3   7
     /
    4   ❌

Il est donc nécessaire de transmettre des limites lors de la récursion.

Il est recommandé d'utiliser directement le parcours inordre pour vérifier qu'il est strictement croissant.