[Easy] Algo challenge #1

[Raul]

Data o structura de date de tip arbore binar de cautare (BST), se cere calcularea sumei valorilor de pe toate nodurile unde valoarea este cuprinsa intre doua numere L si R (inclusiv) si returnarea acesteia.
Se garanteaza ca toate valorile din arbore sunt unice.

* Numarul maxim de noduri din arbore este de 10^4
* Suma calculata si returnata se garanteaza a fi mai mica decat 2^31

EXEMPLU
Input: arbore = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32 (10+15+7)

 

Limbajul care va fi folosit este la alegere libera. Solutiile cu complexitate timp mai mare decat O(N) sunt respinse. O solutie personala va fi pusa ulterior.

Spor!

Edited December 13, 2018 by Raul

[iceposeidon]

struct node{
    int value;
    node *left;
    node *right;
};

long sum(node *root, int a, int b) {
    if(root == NULL)
        return 0;
    if(root->value < a)
        return sum(root->right, a, b);
    if(root->value > b)
        return sum(root->left, a, b);
    return root->value + sum(root->right, a, b) + sum(root->left, a, b);
}

 

Am implementat de distractie rapid in c++, complexitatea este O(n).

 

Sunt curios daca exista solutie mai rapida.

 

[Raul]

Ambele solutii sunt ok.

Nu, nu prea ai ce sa scoti mai rapid de atat, pentru ca trebuie sa treci, totusi, prin toate nodurile arborelui, rezultand, in mod evident, intr-o complexitate timp O(N).

 

Solutia mea (Golang) este urmatoarea (foarte asemenatoare cu ce a facut Gecko):

func helper(root *TreeNode, L, R int, sum *int) {
	if root == nil {
		return
	} else if root.Val >= L && root.Val <= R {
		*sum += root.Val
	}
	helper(root.Left, L, R, sum)
	helper(root.Right, L, R, sum)
}

func sum(root *TreeNode, L int, R int) int {
	var sum int
	helper(root, L, R, &sum)
	return sum
}

 

* Problema este luata si tradusa de pe Leetcode

Edited December 12, 2018 by Raul

[urs]

.

Edited December 12, 2018 by urs
chiar nu am citit atent :(