Loading...

미리보기

전체 9개 스텝 중 3개만 표시

로그인하고 전체 보기

BST 유효성 검사

보통

Validate BST

재귀와 범위 검증을 활용하여 이진 트리가 유효한 BST인지 확인하는 문제

📊 복잡도

구분	복잡도
평균	O(n)
최악	O(n)
공간	O(h)

🏷️ 태그

BST재귀트리범위 검증

📋 문제

데이터베이스 인덱스 검증

데이터베이스의 인덱스가 이진 탐색 트리(BST)로 저장되어 있습니다. 시스템 오류로 인해 인덱스가 손상되었을 수 있습니다. 주어진 트리가 유효한 BST인지 확인하세요.

1/9

Loading...

🔍BST 유효성 검사!

이 트리가 유효한 BST인지 확인해봅시다!

데이터베이스 인덱스 검증

문제 설명

데이터베이스의 인덱스가 이진 탐색 트리(BST)로 저장되어 있습니다. 시스템 오류로 인해 인덱스가 손상되었을 수 있습니다. 주어진 트리가 유효한 BST인지 확인하세요.

입력

이진 트리의 루트 노드

출력

유효한 BST이면 true, 아니면 false

제약 조건

•노드 수: 1 ~ 10,000
•노드 값: -2^31 ~ 2^31 - 1
•왼쪽 서브트리 < 루트 < 오른쪽 서브트리

예제

예제 1

입력

[50, 30, 70, 20, 60, 65, 80]

출력

false

설명

60이 30의 오른쪽 자식이지만 루트(50)보다 크므로 BST 규칙 위반

예제 2

입력

[50, 30, 70, 20, 40, 65, 80]

출력

true

설명

모든 노드가 BST 속성을 만족

BST 유효성 검사 | AlgoNote