Aralık Toplamı

Coddy'nin AVL Tree - Veri Yapıları Serisi #10 kursunda ders 13 / 16.

Ağaç her değeri sıralı tuttuğu için, bir aralığı toplamak için her bir düğümü incelemenize gerek yoktur: bir düğümün değeri low değerinin altındaysa, tüm sol alt ağacı da low değerinin altındadır ve atlanabilir; aynı mantık, bir düğümün değeri high değerinin üzerindeyken sağ alt ağaç için de geçerlidir.

Sadece aralıktaki değerleri içerebilecek alt ağaçlara özyinelemeli olarak giren basit bir in-order dolaşma yeterlidir, ancak bu zorluk için filtre içeren tam bir dolaşma da işe yarar.

Görev

Kolay

low ve high (dahil) değerleri arasında kalan ağaçtaki her bir değerin toplamını döndüren bir rangeSum(tree, low, high) fonksiyonu yazın.

Kendin dene

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