•
문제 설명 : 주어진 트리가 BST인지 반환
•
풀이 방법
◦
아래와 같은 일부 케이스 때문에, 결국 Solution을 확인했는데 생각보다 간단하게 풀 수 있었다.
◦
위 케이스를 분석하자면, 아래와 같이 변경해볼 수 있다.
◦
즉, 다음 노드에 올 수 있는 숫자의 최소값과 최대 값을 설정할 수 있는 것이다.
•
시간복잡도 :
•
성공 코드
# 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 validate(node, low=-float('inf'), high=float('inf')):
# 빈 노드
if not node:
return True
# 설정한 범위 내 노드 값이 설정되지 않은 경우
if node.val <= low or node.val >= high:
return False
# 왼쪽 노드 확인 시, 현재 노드보다 작도록 범위 설정
# 오른쪽 노드 확인 시, 현재 노드보다 크도록 설정
return (validate(node.left, low, node.val) and
validate(node.right, node.val, high))
return validate(root)
Python
복사