Jump to content
Raul

[Easy] Algo challenge #1

Recommended Posts

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 by Raul
  • Upvote 1
Link to comment
Share on other sites

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.

 

Link to comment
Share on other sites

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 by Raul
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.



×
×
  • Create New...