Najniższy wspólny przodek

Lekcja 14 z 16 w kursie Drzewo AVL – struktury danych, seria #10 w Coddy.

Najniższy wspólny przodek dwóch wartości to najgłębszy węzeł, który ma obie z nich gdzieś w swoim poddrzewie. W binarnym drzewie wyszukiwań można go znaleźć bez bezpośredniego porównywania poddrzew: zaczynając od korzenia, jeśli obie wartości są mniejsze od bieżącego węzła, odpowiedź znajduje się gdzieś w lewym poddrzewie; jeśli obie są większe, znajduje się w prawym poddrzewie.

Gdy tylko te dwie wartości znajdą się po różnych stronach (lub jedna z nich będzie równa bieżącemu węzłowi), znajdziesz punkt rozdzielenia: ten węzeł jest najniższym wspólnym przodkiem.

Wyzwanie

Łatwy

Napisz funkcję lca(tree, p, q), która zwraca wartość najniższego wspólnego przodka węzłów p i q. Możesz założyć, że obie wartości istnieją w drzewie.

Spróbuj swoich sił

#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;
}