[Leetcode 98] Validate Binary Search Tree

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

1) 코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        
        def dfs(node, minimum, maximum):
            if not node:
                return True

            if not (minimum < node.val and node.val < maximum):
                return False

            return dfs(node.left, minimum, node.val) and dfs(node.right, node.val, maximum)

        return dfs(root, float('-inf'), float('inf'))

2) 해설

• 이 문제는 Binary Search Tree 여부를 검증하는 문제이다.
• Binary Search Tree는 중위 순회를 했을 때, 값이 오름차순이 되어야 하는 트리를 의미한다.
• 위와 같은 코드가 성립하는 이유는 다음과 같다.
  이진 탐색 트리가 성립하기 위한 조건은 다음과 같다.
  (1) 왼쪽 서브트리의 모든 값은 노드보다 작아야 한다
  (2) 오른쪽 서브트리의 모든 값은 노드보다 커야 한다.
• 따라서 위의 2가지 조건을 기억해서, DFS로 탐색을 하면서,
  만약 조건에 해당하지 않는다면, return False를 해주면 되는 문제이다.