Plus proche ancêtre commun

Leçon 14 sur 16 du cours Arbre AVL - Série Structures de données n°10 de Coddy.

Le plus proche ancêtre commun de deux valeurs est le nœud le plus profond qui possède ces deux valeurs quelque part dans son sous-arbre. Dans un arbre binaire de recherche, vous pouvez le trouver sans jamais comparer directement les sous-arbres : en partant de la racine, si les deux valeurs sont plus petites que le nœud actuel, la réponse se trouve quelque part dans le sous-arbre gauche ; si les deux sont plus grandes, elle se trouve dans le sous-arbre droit.

Au moment où les deux valeurs tombent de côtés différents (ou si l'une d'elles est égale au nœud actuel), vous avez trouvé le point de séparation : ce nœud est le plus proche ancêtre commun.

Défi

Facile

Écrivez une fonction lca(tree, p, q) qui renvoie la valeur de l'ancêtre commun le plus bas de p et q. Vous pouvez supposer que les deux valeurs existent dans l'arbre.

Essayez vous-même

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "avltree.h"
#include "solution.h"

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line1[4096];
    fgets(line1, sizeof(line1), stdin);
    char* tok = strtok(line1, " \n");
    while (tok != NULL) {
        AVLTree_insert(tree, atoi(tok));
        tok = strtok(NULL, " \n");
    }
    char line2[256];
    fgets(line2, sizeof(line2), stdin);
    int p0 = atoi(strtok(line2, " \n"));
    int p1 = atoi(strtok(NULL, " \n"));
    int result = lca(tree, p0, p1);
    printf("%d\n", result);
    return 0;
}