구간 합

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

트리가 모든 값을 정렬된 상태로 유지하기 때문에, 범위의 합을 구하기 위해 모든 노드를 일일이 검사할 필요는 없습니다. 노드의 값이 low보다 작으면 왼쪽 서브트리 전체도 low보다 작으므로 건너뛸 수 있으며, 노드의 값이 high보다 큰 경우 오른쪽 서브트리에도 동일한 논리가 적용됩니다.

범위 내의 값을 포함할 수 있는 서브트리만 재귀적으로 탐색하는 단순한 중위 순회(in-order walk)만으로도 충분하지만, 이 챌린지에서는 필터를 사용한 전체 순회 방식도 가능합니다.

챌린지

쉬움

low와 high를 포함하여 그 사이에 있는 트리의 모든 값의 합을 반환하는 rangeSum(tree, low, high) 함수를 작성하세요.

직접 해보기

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