[LeetCode 해석 및 풀이] 98. Validate Binary Search Tree(이진 검색 트리 검증)

LeetCode 문제 해석 및 풀이 방법

문제 98. Validate Binary Search Tree(이진 검색 트리 검증)

난이도 : 중간🟡 바로가기

 

문 제 설명

영문

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

 

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

 

한글

이진 트리의 root 주어지면 이것이 유효한 이진 검색 트리(BST)인지 확인합니다 .

 

유효한 BST는 다음과 같이 정의됩니다.

• 노드의 왼쪽 하위 트리 에는 해당 노드의 키보다 작은 키를 가진 노드만 포함됩니다.
• 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키를 가진 노드만 포함됩니다.
• 왼쪽 및 오른쪽 하위 트리 도 모두 이진 검색 트리여야 합니다.

 

제한조건

• The number of nodes in the tree is in the range [1, 10⁴].
• -2³¹ <= Node.val <= 2³¹ - 1

 

입출력 예

입력	출력
root = [2,1,3]	true
root = [5,1,4,null,null,3,6]	false

 

해답 및 해설

파이썬 (Python)

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def isValidBSTree(node, lower_bound, upper_bound):
            if not node:
                return True

            return isValidBSTree(node.left, lower_bound, node.val) \
            and isValidBSTree(node.right, node.val, upper_bound) \
            and node.val > lower_bound \
            and node.val < upper_bound

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

 각 노드마다 노드의 값들이 BST의 규칙에 맞는 범위내에 있는지 판별해주면 되는 문제. 처음에는 초기 입력값을 None으로 두고 이리저리 판별을 했었는데, 시간대가 너무 느리게 나와 다른 풀이들을 보니 float("inf")라는 생소한 것을 쓰고 있었다. 이렇게도 되는구나 처음 알게 되었다.