98. Validate Binary Search Tree

Задача

Дан корень бинарного дерева. Определите, является ли оно корректным деревом поиска (BST).

Примеры

Пример 1

Input: root = [2,1,3]
Output: true

Пример 2

Input: root = [5,1,4,null,null,3,6]
Output: false

Пояснение

Значение корня 5, но значение его правого ребёнка 4.

Решение

Решение

// Time Complexity: O(n) - посещаем каждый узел один раз
// Space Complexity: O(h) - глубина стека рекурсии, где h - высота дерева
//                   O(log n) для сбалансированного, O(n) для вырожденного
var isValidBST = function(root) {
    function validate(node, min, max) {
        if (!node) return true;
 
        // Значение узла должно быть строго внутри диапазона
        if (node.val <= min || node.val >= max) return false;
 
        // Левое поддерево: (min, node.val)
        // Правое поддерево: (node.val, max)
        return validate(node.left, min, node.val) &&
            validate(node.right, node.val, max);
    }
 
    return validate(root, -Infinity, Infinity);
};

Решение 2 (Stack)

// Time Complexity: O(n)
// Space Complexity: O(h) - стек для хранения узлов
var isValidBST = function(root) {
    if (!root) return true;
 
    const stack = [{
        node: root,
        min: -Infinity,
        max: Infinity
    }];
 
    while (stack.length > 0) {
        const {
            node,
            min,
            max
        } = stack.pop();
 
        if (node.val <= min || node.val >= max) return false;
 
        if (node.right) {
            stack.push({
                node: node.right,
                min: node.val,
                max: max
            });
        }
        if (node.left) {
            stack.push({
                node: node.left,
                min: min,
                max: node.val
            });
        }
    }
 
    return true;
};