최소 공통 조상

Coddy의 AVL 트리 - 자료구조 시리즈 #10 코스 레슨 — 16개 중 14번째.

두 값의 최소 공통 조상(lowest common ancestor)은 두 값을 모두 자신의 서브트리 어딘가에 포함하고 있는 가장 깊은 노드입니다. 이진 탐색 트리에서는 서브트리를 직접 비교하지 않고도 이를 찾을 수 있습니다. 루트에서 시작하여, 두 값이 모두 현재 노드보다 작으면 정답은 왼쪽 서브트리 어딘가에 있고, 두 값이 모두 크면 오른쪽 서브트리에 있습니다.

두 값이 서로 다른 방향으로 갈라지는 순간(또는 두 값 중 하나가 현재 노드와 일치하는 순간), 분기점을 찾은 것이며 해당 노드가 바로 최소 공통 조상입니다.

챌린지

쉬움

p와 q의 최소 공통 조상(lowest common ancestor)의 값을 반환하는 함수 lca(tree, p, q)를 작성하세요. 두 값은 모두 트리에 존재한다고 가정해도 좋습니다.

직접 해보기

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