Задача 13: Сумма на отрезке двоичного дерева поиск

Напишите функцию rangeSumBST(root, low, high), которая принимает корень бинарного дерева поиска и два целых числа low и high, и возвращает сумму значений всех узлов, чьи значения лежат в диапазоне от low до high (включительно).

Корень бинарного дерева поиска задан объектом класса TreeNode, который уже заготовлен в коде заранее.

Структура класса TreeNode:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val  # Значение узла
        self.left = left  # Левый дочерний узел
        self.right = right  # Правый дочерний узел

Объект TreeNode представляет собой узел дерева с полями(Он заготовлен в вашем коде сткрытно заранее):

• val: значение узла,
• left: ссылка на левое поддерево (или None, если поддерева нет),
• right: ссылка на правое поддерево (или None, если поддерева нет).

Пример 1:

Ввод:

root = [10, 5, 15, 3, 7, null, 18]
low = 7
high = 15

Схема дерева:

        10
       /  \
      5    15
     / \     \
    3   7     18

Вывод:

32

Пояснение:

• Узлы 7, 10 и 15 находятся в диапазоне [7, 15].
• 7 + 10 + 15 = 32.

Пример 2:

Ввод:

root = [10, 5, 15, 3, 7, 13, 18, 1, null, 6]
low = 6
high = 10

Схема дерева:

         10
        /  \
       5    15
      / \   /  \
     3   7 13   18
    /      \
   1        6

Вывод:

23

Пояснение:

• Узлы 6, 7 и 10 находятся в диапазоне [6, 10].
• 6 + 7 + 10 = 23.

Пример использования:

# Пример 1:
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)

print(rangeSumBST(root, 7, 15))  # Ожидаемый вывод: 32

# Пример 2:
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.left = TreeNode(13)
root.right.right = TreeNode(18)
root.left.left.left = TreeNode(1)
root.left.right.left = TreeNode(6)

print(rangeSumBST(root, 6, 10))  # Ожидаемый вывод: 23