Сложность: 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:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rangeSumBST(root, low, high):
if not root:
return 0
if root.val < low:
return rangeSumBST(root.right, low, high)
if root.val > high:
return rangeSumBST(root.left, low, high)
return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high)
Ставь 👍 и забирай 📚 Базу знаний