区間和

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

木はすべての値を順序通りに保持しているため、範囲の合計を求めるためにすべてのノードを検査する必要はありません。ノードの値が low 未満である場合は常に、その左側のサブツリー全体も low 未満となるためスキップできます。ノードの値が high を超えている場合の右側のサブツリーについても、同じ論理が当てはまります。

範囲内の値を含む可能性のあるサブツリーのみを再帰的に探索する単純な通りがけ順（in-order）の探索で十分ですが、このチャレンジでは、フィルターを使用した全探索でも動作します。

チャレンジ

簡単

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