ツリーが有効な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

Nodeをルートとするツリーの最小値と最大値を見つけるの方法を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

は、妥当性チェックを実装する1つの方法で例外をキャッチすることができます

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()