Функция, чтобы определить, является ли дерево допустимым BST?

Question

Мне нужно определить, представлен ли список, представляющий дерево, является ли дерево допустимым BST (этот вопрос берется из leetcode). Я видел другие сообщения об этом, но мне было интересно, может ли кто-нибудь помочь мне с моим подходом, поскольку это явно не так. Например, для дерева [1,2,3], где 1 - корень, 2 - левый ребенок, а 3 - правильный ребенок, мой код возвращает true. Надеюсь, это потребует лишь небольших изменений, но может быть, что подход всей функции неверен.

Вот мой код:

def isValidBST(self, root): 
    if (root == None): 
     return True 
    if (root.left == None or root.left.val < root.val): 
     return self.isValidBST(root.left) 
    if (root.right == None or root.right.val > root.val): 
     return self.isValidBST(root.right) 
    return False 

Во-вторых, я видел подходы с функцией хелперов, которая принимает в мин/макс значения, но это меня смущает. Если кто-то также хотел бы объяснить, почему этот подход является хорошим/лучшим, это было бы очень полезно!

Answer 1

Я сделал бы min_max метод для Node s, который находит минимальные и максимальные значения дерева, укорененного в этом Node. Выполните проверку, находя те здравомыслие, а затем isValidBST может просто поймать исключение

def max_min(self): 

    ''' 
    Returns maximum and minimum values of the keys of the tree rooted at self. 
    Throws an exception if the results are not correct for a BST 
    ''' 

    l_max, l_min = self.left.max_min() if self.left else (self.val, self.val) 
    if l_max > self.val: 
     raise ValueError('Not a BST') 
    r_max, r_min = self.right.max_min() if self.right else (self.val, self.val) 
    if r_min < self.val: 
     raise ValueError('Not a BST') 
    return l_min, r_max 

def isValidBST(self): 
    try: 
     if self.max_min(): 
      return True 
    except ValueError: 
      return False 

Answer 2

Вот один из способов реализации проверки действия:

class BST: 

    def __init__(self, value, left=None, right=None): 
     self.value = value 
     self.left = left 
     self.right = right 

    def isValidBST(self): 
     ''' 
     Simultaneously check for validity and set our own min and max values. 
     ''' 
     self.min = self.max = self.value 
     if self.left: 
      if not self.left.isValidBST(): 
       return False 
      if self.left.max >= self.value: 
       return False 
      self.min = self.left.min 
     if self.right: 
      if not self.right.isValidBST(): 
       return False 
      if self.right.min < self.value: 
       return False 
      self.max = self.right.max 
     return True 

assert BST(2, BST(1), BST(3)).isValidBST() 
case = BST(2, BST(1, None, BST(3))) 
assert case.left.isValidBST() 
assert not case.isValidBST()