← 전체 회차
A-056● Day 562026.07.02mediumleetcode #98neetcode150

이진 탐색 트리 검증

#tree#depth-first-search#binary-search-tree#binary-tree
↗ leetcode #98 · validate-binary-search-tree
01

문제

· problem
P.056

이진 탐색 트리 검증

↗ leetcode #98

이진 트리의 루트가 주어졌을 때, 이것이 유효한 이진 탐색 트리(BST)인지 판단하세요. 유효한 BST는 다음과 같이 정의됩니다: - 노드의 왼쪽 서브트리는 노드의 키보다 작은 키를 가진 노드들만 포함합니다. - 노드의 오른쪽 서브트리는 노드의 키보다 큰 키를 가진 노드들만 포함합니다. - 왼쪽 서브트리와 오른쪽 서브트리도 모두 이진 탐색 트리여야 합니다.

제약
  • · 1 ≤ number of nodes ≤ 10⁴
  • · -2³¹ ≤ Node.val ≤ 2³¹ - 1
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[2,1,3]
true
example 2input → output
[5,1,4,null,null,3,6]
false
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    엄격한 부등호(< 및 >)는 중복값이 허용되지 않는다는 의미인가요?
  • ☐
    왼쪽 서브트리 전체가 조건을 만족해야 하나요, 아니면 직접 자식만 확인하면 되나요?
  • ☐
    트리가 비어있거나 노드가 하나만 있으면 유효한 BST로 간주되나요?
  • ☐
    음수 값을 가진 노드도 검증할 수 있나요?
  • ☐
    검증 중에 트리의 구조를 수정할 수 있나요?
  • ☐
    검증 결과로 유효하지 않은 노드의 목록을 반환해야 하나요?
  • ☐
    범위(left, right)가 가능한 모든 값을 포함해야 하나요?
  • ☐
    트리의 높이를 계산해야 하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 헬퍼 함수 정의
○
def valid(node, left, right):
○
def isValid(node):
○
def check(node, limit):
step 2· 기저 케이스: 공 노드 처리│ 중첩
○
return True
○
return False
○
return node is not None
step 3· 현재 노드 범위 검증│ 중첩
○
if not (left < node.val < right):
○
if not (left <= node.val <= right):
○
if node.val < left and node.val > right:
step 4· 왼쪽 서브트리 검증│ 중첩
○
return valid(node.left, left, node.val) and valid(
○
valid(node.left, left, node.left)
○
valid(node.left, node.val, right)
step 5· 오른쪽 서브트리 검증│ 중첩
○
node.right, node.val, right
○
valid(node.right, node.right, right)
○
valid(node.right, left, node.val)
step 6· 무한 경계로 재귀 시작
○
return valid(root, float("-inf"), float("inf"))
○
return valid(root, 0, float('inf'))
○
return valid(root, float('-inf'), 0)
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, val=0, left=None, right=None):
4
#         self.val = val
5
#         self.left = left
6
#         self.right = right
7
class Solution:
8
    def isValidBST(self, root: TreeNode) -> bool:
9
        def valid(node, left, right):
10
            if not node:
11
                return True
12
            if not (left < node.val < right):
13
                return False
14
15
            return valid(node.left, left, node.val) and valid(
16
                node.right, node.val, right
17
            )
18
19
        return valid(root, float("-inf"), float("inf"))
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[2,1,3]
→
true
case 2
[5,1,4,null,null,3,6]
→
false
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.