Условие задачи

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

Валидное BST определяется следующим образом:

• Левое поддерево узла содержит только узлы с ключами меньше, чем ключ узла.
• Правое поддерево узла содержит только узлы с ключами больше, чем ключ узла.
• И левое, и правое поддеревья также должны быть бинарными деревьями поиска.

Примеры

• Пример 1:

      2
     / \\\\
    1   3
  
  

  В этом примере корень дерева - узел с ключом 2. Левое поддерево содержит только узел с ключом 1, который меньше ключа корня, а правое поддерево содержит только узел с ключом 3, который больше ключа корня. Оба поддерева также являются деревьями поиска. Значит, данное дерево является валидным BST.

• Пример 2

      5
     / \\\\
    1   4
       / \\\\
      3   6
  
  

  В этом примере корень дерева - узел с ключом 5. Левое поддерево содержит только узел с ключом 1, который меньше ключа корня, а правое поддерево содержит узел с ключом 4, который меньше ключа корня, и поддерево, которое не является деревом поиска, т.к. узел 6 больше ключа корня 5, но меньше ключа узла 4. Значит, данное дерево не является валидным BST.

Решение

Для решения этой задачи мы будем использовать рекурсивный алгоритм, который будет проверять каждый узел дерева на соответствие требованиям BST. Мы будем передавать в функцию максимальный и минимальный допустимые значения узла. Изначально мы передадим функции float('-inf') и float('inf') для максимального и минимального значений соответственно. Если мы достигнем листового узла, то вернем True, а иначе будем рекурсивно проверять значения левого и правого поддерева.

Код

class Solution:
    def isValidBST(self, root, min_val=float('-inf'), max_val=float('inf')):
        if not root:
            return True
        if root.val <= min_val or root.val >= max_val:
            return False
        return self.isValidBST(root.left, min_val, root.val) and self.isValidBST(root.right, root.val, max_val)