Задача: 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], включить значение узла в сумму и рекурсивно искать в обоих поддеревьях.

😎 Решение:

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

class Solution {
    func rangeSumBST(_ root: TreeNode?, _ low: Int, _ high: Int) -> Int {
        guard let root = root else { 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)
    }
}

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