Ежедневная часть (e) C++ # 93, Распространенная проблема на собеседовании: проверка BST
Сегодня мы рассмотрим распространенную проблему интервью C++: проверка BST.
Учитывая бинарное дерево, подтвердите, что это бинарное дерево поиска.
- для каждого узла все узлы в левом поддереве имеют строго меньшие значения
- для каждого узла все узлы в правом поддереве имеют строго более высокие значения
В приведенном выше примере дерево не является допустимым бинарным деревом поиска, поскольку условие правого поддерева нарушается между узлами 8 и 7.
Прежде чем вы продолжите читать решение, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/WKe14x93v.
Решение
Если мы проверяем конкретный узел в двоичном дереве поиска, переход к левому поддереву устанавливает верхнюю границу для всех значений в поддереве, а переход к правому поддереву устанавливает нижнюю границу для всех значений в поддереве.
Нам нужно отслеживать эти границы, когда мы исследуем дерево, используя предварительный обход. Дерево является действительным бинарным деревом поиска, если мы не находим нарушения, и недействительным, если мы его находим.
// pre-order traversal with bounds
bool is_valid_bst(Node* root, int min, int max) {
// Is this node within the bounds?
if (root->value > max || root->value < min)
return false;
// Explore left subtree with the updated bounds
if (root->left != nullptr) {
if (root->value == INT_MIN) // avoid underflow
return false;
if (!is_valid_bst(root->left, min, root->value - 1))
return false;
}
// Explore right subtree with the updated bounds
if (root->right != nullptr) {
if (root->value == INT_MAX) // avoid overflow
return false;
if (!is_valid_bst(root->right, root->value + 1, max))
return false;
}
return true;
}
bool is_valid_bst(const Tree& tree) {
// Root can be any value
return is_valid_bst(tree.root, INT_MIN, INT_MAX);
}
