Leetcode # 98. Validate Binary Search Tree

https://leetcode.com/problems/validate-binary-search-tree/

Solution

Time Complexity: O(len(BST))
Space Complexity: O(len(BST))
(The input and output generally do not count towards the space complexity.)

 如下，直接修改 cond 是不可以的，
因為同一個 node 的左右兩子樹都會使用到原始 cond 做合格與否的判斷

while stack:
  # condition := (lower_limit, upper_limit)
  cur, cond = stack.pop()
  if cur.left:
    cond[1] = min(cond[1], cur.val)
    if cur.left.val <= cond[0] or cur.left.val >= cond[1]:
      return False
    stack.append([cur.left, cond])
  if cur.right:
    cond[0] = [max(cond[0], cur.val), cond[1]]
    if cur.right.val <= cond[0] or cur.right.val >= cond[1]:
      return False
    stack.append([cur.right, cond])

class Solution:
  def isValidBST(self, root: Optional[TreeNode]) -> bool:
    stack = [[root, [-float("inf"), float("inf")]]]
    while stack:
      # condition := (lower_limit, upper_limit)
      cur, cond = stack.pop()
      if cur.left:
        _cond = [cond[0], min(cond[1], cur.val)]
        if cur.left.val <= _cond[0] or cur.left.val >= _cond[1]:
          return False
        stack.append([cur.left, _cond])
      if cur.right:
        _cond = [max(cond[0], cur.val), cond[1]]
        if cur.right.val <= _cond[0] or cur.right.val >= _cond[1]:
          return False
        stack.append([cur.right, _cond])

    return True

Last Updated on 2023/08/16 by A1go