Код Middle Деревья обновлено
Сумма значений в диапазоне
Условие
Сумма значений узлов дерева поиска, попадающих в диапазон [low, high] включительно. Если low больше high - ноль.
Что проверяют тесты
диапазон внутри
весь диапазон
перевёрнутый диапазон
пустое дерево
Как подойти
Отсечение веток по свойству дерева поиска - то, ради чего задача даётся. Полный обход тоже даст правильный ответ, но за O(n) вместо O(глубины + число попавших узлов). Уметь объяснить, почему левую ветку можно не смотреть, важнее, чем написать код.
Подсказки: 2
- Свойство дерева поиска позволяет не заходить в заведомо ненужные ветки.
- Если значение узла меньше нижней границы, вся левая ветка тоже меньше.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.