[1스4코2파] # 210 LeetCode 98. Validate Binary Search Tree

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (210차)
[4코1파] 2023.01.13~ (202일차)
[1스4코1파] 2023.04.12~ (113일차)
[1스4코2파] 2023.05.03 ~ (91일차)

Today :

2023.08.02 [210일차]
Tree
98. Validate Binary Search Tree

98. Validate Binary Search Tree

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

문제 설명

binary tree가 주어졌을때, valid BST 인지 확인하는데,
BST는 왼쪽노드 값 < 중간노드 값 < 오른쪽 노드 값인 노드이다.

문제 풀이 방법

dfs로 탐색하면서, root 노드와 아래 node의 값을 비교하면서 계속 내려간다.
이때 포인트는 노드를 비교할 때 기준이 되는 노드의 왼쪽 ,오른쪽 범위를 left와 중간 노드, right 노드 값으로 치환하면서 내려가야 한다는 것임

내 코드

 # 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 valid(node, left, right):
            if not node:
                return True
            
            if not (node.val < right and node.val > left):
                return False

            return (valid(node.left, left, node.val) and valid(node.right, node.val, right))

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

증빙

여담