Problème : Étant donné les séquences de parcours préfixe (pré-ordre) et infixe (en-ordre) d'un arbre binaire, calculer la hauteur de l'arbre.

Format d'entrée : La première ligne contient un entier N (≤50) représentant le nombre total de nœuds. Les deux lignes suivantes contiennnent respectivement les séquences préfixe et infixe, chacune de longueur N, composées de lettres anglaises uniques (la casse compte).

Format de sortie : Un entier unique correspondant à la hauteur de l'arbre.

Exemple d'entrée :

9
ABDFGHIEC
FDHGIBEAC

Exemple de sortie :

5

Analyse : La solution exploite la relation entre les parcours préfixe et infixe. Le premier caractère de la séquence préfixe est toujours la racine. En localisant cette racine dans la séquence infixe, on peut délimiter les sous-arbres gauche et droit. On applique ensuite récursivement ce processus pour chaque sous-arbre, en mesurant la profondeur maximale.

Implémentation en C : L'algorithme récursif suivant calcule la hauteur. Il détermine la racine, sépare les sous-arbres, puis renvoie la hauteur maximale entre le sous-arbre gauche et le sous-arbre droit, augmentée de 1.

#include <stdio.h>
#include <string.h>

int locateRoot(char target, const char *sequence, int start, int end) {
    for (int pos = start; pos < end; pos++) {
        if (sequence[pos] == target) {
            return pos;
        }
    }
    return -1;
}

int computeTreeHeight(const char *preorder, const char *inorder, int length) {
    if (length == 0) {
        return 0;
    }
    
    char currentRoot = preorder[0];
    int rootIdx = locateRoot(currentRoot, inorder, 0, length);
    int leftSize = rootIdx;
    int rightSize = length - rootIdx - 1;
    
    int leftHeight = computeTreeHeight(preorder + 1, inorder, leftSize);
    int rightHeight = computeTreeHeight(preorder + leftSize + 1, inorder + rootIdx + 1, rightSize);
    
    int maxHeight = leftHeight > rightHeight ? leftHeight : rightHeight;
    return maxHeight + 1;
}

int main() {
    int nodeCount;
    scanf("%d", &nodeCount);
    
    char preSeq[52];
    char inSeq[52];
    scanf("%s %s", preSeq, inSeq);
    
    int height = computeTreeHeight(preSeq, inSeq, nodeCount);
    printf("%d\n", height);
    
    return 0;
}

La fonction locateRoot recherche la position d'un nœud dans la séquence infixe, tandis que computeTreeHeight divise récursivement le problème. La complexité temporelle est O(n²) dans le pire des cas, ce qui convient pour N ≤ 50.