Бинарное дерево поиска

Решение

Подход

Для проверки BST нужно убедиться, что для каждого узла выполняются ограничения: значение больше всех элементов в левом поддереве и меньше всех в правом. Ключевая идея — отслеживать диапазон допустимых значений для каждого узла.

Структура узла дерева

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

Оптимальное решение (O(1) память, O(n) время)

func isValidBST(_ root: TreeNode?) -> Bool {
    return isValidBSTHelper(root, min: Int.min, max: Int.max)
}

func isValidBSTHelper(_ node: TreeNode?, min: Int, max: Int) -> Bool {
    // Пустой узел — это валидный BST
    guard let node = node else { return true }
    
    // Проверяем, что значение узла в допустимом диапазоне
    if node.val <= min || node.val >= max {
        return false
    }
    
    // Проверяем левое поддерево (max становится текущим значением)
    // Проверяем правое поддерево (min становится текущим значением)
    return isValidBSTHelper(node.left, min: min, max: node.val) &&
           isValidBSTHelper(node.right, min: node.val, max: max)
}

Почему это работает:

1. Для левого поддерева все значения должны быть < node.val, поэтому max = node.val
2. Для правого поддерева все значения должны быть > node.val, поэтому min = node.val
3. Диапазон [min, max) сужается при спуске по дереву

Альтернативное решение (In-order обход)

В BST in-order обход дает отсортированный массив значений:

func isValidBSTInOrder(_ root: TreeNode?) -> Bool {
    var prev: Int? = nil
    var isValid = true
    
    func inorder(_ node: TreeNode?) {
        guard let node = node else { return }
        
        inorder(node.left)
        
        // Проверяем, что текущий элемент больше предыдущего
        if let prev = prev, node.val <= prev {
            isValid = false
            return
        }
        prev = node.val
        
        inorder(node.right)
    }
    
    inorder(root)
    return isValid
}

Решение с использованием очереди (BFS, O(n) память)

Если нужно избежать рекурсии:

func isValidBSTBFS(_ root: TreeNode?) -> Bool {
    guard let root = root else { return true }
    
    var queue: [(node: TreeNode, min: Int, max: Int)] = []
    queue.append((root, Int.min, Int.max))
    
    while !queue.isEmpty {
        let (node, min, max) = queue.removeFirst()
        
        if node.val <= min || node.val >= max {
            return false
        }
        
        if let left = node.left {
            queue.append((left, min, node.val))
        }
        
        if let right = node.right {
            queue.append((right, node.val, max))
        }
    }
    
    return true
}

Тестирование

// Тест 1: Валидный BST
let tree1 = TreeNode(5)
tree1.left = TreeNode(3)
tree1.right = TreeNode(7)
tree1.left?.left = TreeNode(1)
tree1.left?.right = TreeNode(4)
tree1.right?.left = TreeNode(6)
tree1.right?.right = TreeNode(8)

print(isValidBST(tree1))  // true

// Тест 2: Невалидный BST (6 в левом поддереве узла 5)
let tree2 = TreeNode(5)
tree2.left = TreeNode(3)
tree2.right = TreeNode(7)
tree2.left?.left = TreeNode(1)
tree2.left?.right = TreeNode(6)  // Ошибка!

print(isValidBST(tree2))  // false

// Тест 3: Граничный случай
let tree3 = TreeNode(Int.min)
tree3.right = TreeNode(Int.max)
print(isValidBST(tree3))  // true (если нет переполнения)

// Тест 4: Один узел
let tree4 = TreeNode(42)
print(isValidBST(tree4))  // true

Анализ решений

*h — высота дерева (для сбалансированного дерева h = O(log n), в худшем случае h = O(n)) **w — максимальная ширина дерева

Важные моменты

1. Int.min / Int.max: Если используются граничные значения, нужно быть осторожным. Можно использовать Optional<Int> вместо Int

2. Рекурсия vs Итерация: Рекурсия проще для дерева, но может привести к stack overflow для очень глубоких деревьев

3. Ошибка в наивном подходе:

// ❌ НЕПРАВИЛЬНО!
func isValidBSTWrong(_ node: TreeNode?) -> Bool {
    guard let node = node else { return true }
    
    // Проверяем только прямых детей!
    if let left = node.left, left.val >= node.val { return false }
    if let right = node.right, right.val <= node.val { return false }
    
    return isValidBSTWrong(node.left) && isValidBSTWrong(node.right)
}
// Это не работает! Например, левый потомок узла 5 может быть 3 < 5, 
// но его правое поддерево может содержать 6 > 5

Рекомендация для интервью

Используйте первое решение (min-max диапазон):

• Легче объяснить интервьюеру
• Показывает понимание BST свойств
• Не требует дополнительной памяти (кроме стека рекурсии)
• Если интервьюер просит оптимизацию, переходите на BFS

Использование Int.min/Int.max может вызвать уточняющие вопросы. Лучше сказать: "Можно использовать Optional<Int> для более надёжного решения".