Дано корінь бінарного дерева, і завдання полягає в тому, щоб визначити, чи є це дерево правильним бінарним деревом пошуку (BST).
Правильне BST має такі характеристики:
- Ліва піддерева кожного вузла повинна містити лише вузли з меншими значеннями, ніж сам вузол.
- Права піддерева повинна містити лише вузли з більшими значеннями, ніж сам вузол.
Обидва піддерева також повинні бути правильними бінарними деревами пошуку.
Приклад 1:
Кредит: Leetcode
Вхід: root = [2,1,3]
Вихід: true
Приклад 2:
Кредит: Leetcode
Вхід: root = [5,1,4,null,null,3,6]
Вихід: false
Пояснення: Значення кореня — 5, але правий нащадок має значення 4, що суперечить правилу.
Підхід
Для вирішення цієї задачі необхідно визначити діапазони допустимих значень для кожного вузла дерева. Ми будемо використовувати мінімальні і максимальні значення для кожного вузла, щоб перевірити, чи підходить поточне значення.
Ми починаємо з ініціалізації мінімального значення як мінімум з типу long long, а максимального — як максимум з цього ж типу. Це потрібно, оскільки при перевірці значень ми маємо справу з великими числами, такими як -2³¹ і 2³¹-1.
Якщо поточний вузол порожній, то ми вважаємо це правильним BST.
Далі перевіряємо, чи знаходиться значення поточного вузла в діапазоні між мінімумом і максимумом. Якщо ні — повертаємо false.
Крім того, необхідно перевірити ліві і праві піддерева. Для лівого піддерева максимальне значення буде обмежено значенням поточного вузла, а для правого мінімальне значення буде обмежене значенням вузла. Якщо хоча б одне піддерево не є правильним, повертаємо false.
В кінці, якщо всі перевірки пройшли успішно, повертаємо true.
Код
class Solution {
public:
bool isValidBST(TreeNode* root) {
return isValidBSThelper(root, numeric_limits::min(), numeric_limits::max());
}
private:
bool isValidBSThelper(TreeNode* node, long long min, long long max)
{
if (!node) { return true; }
if (node->val <= min || node->val >= max)
{
return false;
}
if (!isValidBSThelper(node->left, min, node->val))
{
return false;
}
if (!isValidBSThelper(node->right, node->val, max))
{
return false;
}
return true;
}
};
Аналіз складності
Часова складність: O(N) (лінійна), оскільки в найгіршому випадку потрібно пройти все дерево.
Просторова складність: O(N) через використання рекурсивного стека.
Відео пояснення
Перекладено з: Leetcode 98 — Validate Binary Search Tree | BST | DFS | C++ | LC Medium | Cpp Interview Problem