[코테] 리트코드 파이썬 98번 Validate Binary Search Tree

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

 

 

해당 문제는 이진 탐색 트리의 조건에 해당하는 트리인지 아닌지를 리턴하는 문제이다. left 노드의 값이 해당 노드보다 더 작아야하고, right 노드의 값이 더 커야 한다.

 

첫 시도에서는, root를 재귀적으로 호출하여 왼쪽 노드와의 값을 비교하고 왼쪽으로 타고 내려가며 확인하는 방법으로 풀고자하였다. root가 None이 될 때, 즉 왼쪽 leaf 노드로 갈 경우 오른쪽 노드로 옮겨가 확인하지 않고 리턴해 버리는 문제가 있었다.

# 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(root):
            if root is None:
                return
            print(root.val)

            if root.left is not None and root.left.val>root.val:
                return False
            elif root.left is None:
                return
            else:
                root=root.left
                check(root)

            if root.right is not None and root.right.val<root.val:
                return False
            elif root.right is None:
                return
            else:
                root=root.right
                check(root)

        check(root)
        return True

 

최종 답안은 다음과 같다. 재귀 함수의 리턴값으로 왼쪽 노드를 호출하는 부문과 오른쪽 노드를 호출하는 부문을 나누어 처리한다. 이를 통해 두 방향 모두 조건을 만족해야 통과할 수 있게끔 구성할 수 있다.

왼편을 처리할 때는 현재 노드의 값을 max로 하여, 현재 노드 값보다 더 커진다면 False가 되게끔 한다.

오른편을 처리할 때도 마찬가지로 현재 노드의 값을 min으로 하여, 현재 노드 값보다 작아진다면 False가 되게끔 한다.

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def check(root, min_val, max_val):
            if root is None:
                return True
            
            if root.val <= min_val or root.val >= max_val:
                return False
            
            return (check(root.left, min_val, root.val) and
                    check(root.right, root.val, max_val))

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