En Düşük Ortak Ata

Coddy'nin AVL Tree - Veri Yapıları Serisi #10 kursunda ders 14 / 16.

İki değerin en düşük ortak atası, her iki değeri de kendi alt ağacında barındıran en derin düğümdür. Bir ikili arama ağacında, bunu alt ağaçları doğrudan karşılaştırmadan bulabilirsiniz: kökten başlayarak, her iki değer de mevcut düğümden küçükse cevap sol alt ağaçta bir yerdedir; her ikisi de daha büyükse sağ alt ağaçtadır.

İki değerin farklı taraflara düştüğü (veya birinin mevcut düğüme eşit olduğu) an, ayrılma noktasını bulmuşsunuzdur: o düğüm en düşük ortak atadır.

Görev

Kolay

p ve q değerlerinin en düşük ortak atasının (lowest common ancestor) değerini döndüren bir lca(tree, p, q) fonksiyonu yazın. Her iki değerin de ağaçta mevcut olduğunu varsayabilirsiniz.

Kendin dene

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