[medium] 98. Validate Binary Search Tree

문제

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

Validate Binary Search Tree - LeetCode

---

풀이방법

root부터 시작해서 최소값, 최대값을 저장하면서 children이 범위 내에 있는지 확인하면 되는 문제이다.

right children을 탐색할 때는 최대값을 업데이트하고, left children을 탐색하다가 최소값을 업데이트 한다. 

최소값, 최대값을 업데이트하면서 범위내에 해당 노드의 값이 존재하는지 확인하다가, 조건에 만족하지 못하는 경우 False를 리턴한다.

반응형

---

코드

# 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 check(node, minval, maxval):
            if not node:
                return True
            if not minval<node.val<maxval:
                return False
            if node.left:
                if not check(node.left,  minval, min(node.val, maxval)):
                    return False
            if node.right:
                if not check(node.right, max(node.val, minval), maxval):
                    return False
            return True
        
        result = check(root.left, -float('inf'), root.val)
        if not result:
            return result
        else:
            result = check(root.right, root.val, float('inf'))
        return result