[Leetcode][Python] 98. Validate Binary Search Tree

리트코드 / 파이썬 / 98. Validate Binary Search Tree

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

Validate Binary Search Tree - LeetCode

문제 풀이

입력 받은 Binary Search Tree의 valid 여부를 출력하는 문제다.

 

root의 모든 left node들은 root보다 작아야 하고,

root의 모든 right node들은 root보다 커야 한다.

 

왼쪽 node를 탐색하는 경우 root value가 max가 되고,

오른쪽 node를 탐색하는 경우 root value가 min이 된다. 

 

아래 그림과 같이 말이다. 

 

 

소스 코드

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def isValidBST(self, root):
        """
        https://leetcode.com/problems/validate-binary-search-tree/
        :type root: TreeNode
        :rtype: bool
        """
        return self.isValidate(root, None, None)

    def isValidate(self, root, min, max):
        if not root:
            # if it is a leaf node
            return True
        elif (min is not None and min >= root.val) or (max is not None and max <= root.val):
            # if it doesn't satisfy the min/max range
            # warning: if check Integer type if it is None or not, 
            #          avoid using just 'min' instead of 'min is not None'
            #          cause 'min' returns False if it contains '0'
            return False
        else:
            # traverse left/right node each
            return self.isValidate(root.left, min, root.val) and self.isValidate(root.right, root.val, max)