98. Validate Binary Search Tree

Question: Validate Binary Search Tree

Solution

想法：是否每一個 node 都滿足 left < node < right → DST

要特別注意的是，node 左邊的值「都要」小於 node，右邊的值「都要」大於 node

所以每次往下檢查 children 值的時候，如果是往左邊檢查，left children 必須都要 < node

也就是 left children 會有一個 upper bound，upper bound 會是該 node。lower bound 延續 node 原本的 lower bound。

右邊同理，如果是檢查 right children，right children 必須都要 > node，也就是 right children 會有一個 lower bound。upper bound 延續 node 的 upper bound。

• recursive 的兩個條件：
  1. 終止條件：
     1. 如果一直往下找，找到 node 不存在時，代表該 node 一定是 valid，因為底下沒人可以比較: if node == None: return True
  2. 遞回條件: def check_valid(如上述，需要 lower bound & upper bond)：
     • 要滿足:
       1. left child < node < right.child
       2. 往左走的話，左邊的高標會變成 node: upper bound = node.val，低標維持
          1. check_valid(node.left, lower bound, node.val)
       3. 往右走的話，右邊的低標會變成 node: lower bound = node.val，高標維持
          1. check_valid(node.right, node.val, upper bound)

Time Complexity O(2N)

class Solution:

def isValidBST(self, root: Optional[TreeNode]) -> bool:

def check_valid(node, lower_bound, upper_bound):

if node == None:

return True

if not (lower_bound < node.val and node.val < upper_bound):

return False

return check_valid(node.left, lower_bound, node.val) and check_valid(node.right, node.val, upper_bound)

return check_valid(root, -float("inf"), float("inf"))

Video Solution