105. Construction d'un arbre binaire à partir des séquences de parcours préfixe et infixe

Approche itérative avec pile

Principes

• Dans le parcours préfixe, pour deux nœuds adjacents u et v, le nœud v est soit le fils gauche de u, soit le fils droit d'un ancêtre de u
• Pour une chaîne sans nœud droit, le parcours infixe va des feuilles à la racine, tandis que le parcours préfixe va de la racine aux feuilles

Méthode de résolution

1. Utiliser une pile pour maintenir les nœuds du parcours préfixe
2. Utiliser un pointeur p指向le premier nœud feuille du parcours infixe
3. Parcourir la séquence préfixe jusqu'au nœud feuille pointé par p, ces nœuds sont continuellement les fils gauches de leur parent, on les empile simplement.
4. Si le nœud précédent dans le parcours est le nœud feuille pointé par p, alors le nœud actuel est le fils droit d'un nœud dans la chaîne (pile). Comment trouver son parent ?
5. Déplacer le pointeur p vers la droite dans le parcours infixe, tout en remontant dans la chaîne (pile) pour trouver le dernier nœud correspondant, qui sera son parent.

class Solution {
    public Arbre constructArbre(int[] preordre, int[] inordre) {
        Arbre racine = new Arbre(preordre[0]);
        Pile<Arbre> pile = new Pile<>();
        pile.empiler(racine);
        int indiceIn = 0;
        Arbre courant = racine;
        for(int i = 1; i < preordre.length; ++ i) {
            if(preordre[i - 1] != inordre[indiceIn]) {
                courant.gauche = new Arbre(preordre[i]);
                pile.empiler(courant.gauche);
                courant = courant.gauche;
            } else {
                while(!pile.estVide() && pile.sommet().val == inordre[indiceIn]) {
                    courant = pile.depiler();
                    indiceIn ++ ;
                }
                courant.droit = new Arbre(preordre[i]);
                pile.empiler(courant.droit);
                courant = courant.droit;
            }
        }
        return racine;
    }
}

Approche récurrsive

• La racine du sous-arbre dans le parcours préfixe a des intervalles de sous-arbres gauche et droit dont la somme des longueurs correspond à celle dans le parcours infixe

1. Le premier nœud d'un intervalle dans le parcours préfixe est toujours la racine
2. Localiser la position de la racine dans le parcours infixe, l'intervalle du sous-arbre gauche est à gauche, celui du sous-arbre droit est à droite, d'où on obtient les longueurs des intervalles des sous-arbres
3. À partir des longueurss obtenues, localiser les intervalles correspondants dans le parcours préfixe
4. Construire récursivement les deux sous-arbres

class Solution {
    Map<Integer, Integer> dictionnaire;
    
    public Arbre construireArbre(int[] preordre, int[] inordre) {
        dictionnaire = new HashMap<>();
        for(int i = 0; i < inordre.length; ++ i) {
            dictionnaire.put(inordre[i], i);
        }
        return construire(preordre, 0, preordre.length-1, 0, preordre.length-1);
    }

    public Arbre construire(int[] preordre, int preGauche, int preDroite, int inGauche, int inDroite) {
        int val = preordre[preGauche];
        Arbre racine = new Arbre(val);
        if(preGauche == preDroite) return racine;
        int indiceIn = dictionnaire.get(val);
        int tailleGauche = indiceIn - inGauche;
        int tailleDroite = inDroite - indiceIn;

        if(tailleGauche > 0) racine.gauche = construire(preordre, preGauche + 1, preGauche + tailleGauche, indiceIn - tailleGauche, indiceIn - 1);
        if(tailleDroite > 0) racine.droit = construire(preordre, preGauche + tailleGauche + 1, preDroite, indiceIn + 1, indiceIn + tailleDroite);

        return racine;
    }
}