Выбор ответа Middle Деревья спрашивают часто обновлено
Проверка BST: ошибка
Вопрос
Функция проверяет, что дерево это BST. Почему она неверна?
function isBST(node) {
if (!node) return true;
if (node.left && node.left.val >= node.val) return false;
if (node.right && node.right.val <= node.val) return false;
return isBST(node.left) && isBST(node.right);
}
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Проверяет только детей, а всё левое поддерево должно быть меньше узла. Дерево 5 (левый 3 (правый 7)) пройдёт проверку: 3 < 5 и 7 3, но 7 в левом поддереве пятёрки.
Варианты ответа
- Проверяет только детей, а всё левое поддерево должно быть меньше узлаправильный ответ
- Она верна: проверка детей каждого узла рекурсивно покрывает всё
- Нужно сравнивать через
<=вместо<, иначе дубликаты ломают ответ - Рекурсия не обходит правое поддерево из-за раннего
return
Разбор
Дерево 5 (левый 3 (правый 7)) пройдёт проверку: 3 < 5 и 7 > 3, но 7 в левом поддереве пятёрки. Правильно передавать границы (node, lo, hi) или проверять, что in-order обход строго возрастает.
- Функция неверна, пример выше.
- Строгость сравнения не исправит главную ошибку.
- Правое поддерево обходится.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.