最小共通祖先

Coddyの「AVL Tree - データ構造シリーズ #10」コースのレッスン 14/16。

2つの値の最小共通祖先とは、その両方の値を自身の部分木の中に持つ、最も深いノードのことです。二分探索木では、部分木を直接比較することなくこれを見つけることができます。ルートから始めて、両方の値が現在のノードよりも小さい場合、答えは左の部分木のどこかにあります。両方の値が大きい場合は、右の部分木にあります。

2つの値が異なる側に分かれた瞬間（または一方が現在のノードと等しくなった瞬間）、分岐点が見つかったことになります。そのノードが最小共通祖先です。

チャレンジ

簡単

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