K번째로 작은 원소

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

다음 챌린지들은 방금 빌드한 완성된 AVLTree 클래스를 사용하며, 이는 잠긴 파일로 제공됩니다. 각 챌린지는 트리를 사용하는 함수를 작성하는 새로운 solution 파일을 제공합니다.

모든 이진 탐색 트리(회전은 이를 변경하지 않음)의 중위 순회(in-order traversal)는 값을 정렬된 순서로 방문합니다. 따라서 k번째로 작은 값은 해당 순회의 인덱스 k - 1에 있는 요소입니다.

챌린지

쉬움

트리에서 k번째로 작은 값을 반환하는 kthSmallest(tree, k) 함수를 작성하세요 (1-기반 인덱스). k는 유효하다고 가정할 수 있습니다.

직접 해보기

#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 result = kthSmallest(tree, p0);
    printf("%d\n", result);
    return 0;
}