Задача: 938. Range Sum of BST
Сложность: easy

Учитывая корневой узел двоичного дерева поиска и два целых числа low и high, верните сумму значений всех узлов со значением в диапазоне [low, high].

Пример:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32

👨‍💻 Алгоритм:

1⃣Если дерево пустое, вернуть 0.

2⃣Если значение текущего узла меньше low, рекурсивно искать в правом поддереве.
Если значение текущего узла больше high, рекурсивно искать в левом поддереве.

3⃣Если значение текущего узла в диапазоне [low, high], включить значение узла в сумму и рекурсивно искать в обоих поддеревьях.

😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    function rangeSumBST($root, $low, $high) {
        if ($root === null) return 0;
        if ($root->val < $low) return $this->rangeSumBST($root->right, $low, $high);
        if ($root->val > $high) return $this->rangeSumBST($root->left, $low, $high);
        return $root->val + $this->rangeSumBST($root->left, $low, $high) + $this->rangeSumBST($root->right, $low, $high);
    }
}

Ставь 👍 и забирай 📚 Базу знаний