Validate Binary Search Tree
레벨 순서로 배열 tree에 저장된 이진 트리가 주어집니다. 루트는 인덱스 0에 있고, 인덱스 i에 있는 노드의 자식은 2*i+1(왼쪽)과 2*i+2(오른쪽)에 있으며, -1은 비어 있는 위치를 나타내고, 배열은 끝에 여분의 -1 항목이 있을 수 있습니다.
isValidBST라는 함수를 작성하세요. 트리가 이진 탐색 트리이면 true를 반환하고, 그렇지 않으면 false를 반환합니다. 이진 탐색 트리에서는 모든 노드의 값이 왼쪽 하위 트리의 모든 값보다 엄격히 크고 오른쪽 하위 트리의 모든 값보다 엄격히 작아야 합니다. 유효한 트리에는 같은 값이 두 개 있을 수 없습니다.
함수
- treeinteger-array
- 이진 트리를 레벨 순서로 나타내며, 빈 자리는 -1로 표시합니다
- 반환값boolean
- 트리가 이진 탐색 트리이면 true이고, 그렇지 않으면 false입니다
제약 조건
1 ≤ tree.length ≤ 32767- 각
tree[i]는-1이거나0 ≤ tree[i] ≤ 105인 값입니다. tree[0]는 절대-1이 아니므로 트리에는 노드가 하나 이상 있습니다.- 배열은 마지막 노드 이후에
-1항목이 더 포함된 채 끝날 수 있습니다. - 빈 자리의 두 자식도 모두 비어 있고, 깊이는 최대
14입니다. - 값은 반복될 수 있습니다.
예제
- 입력
- tree = [8, 3, 12, 1, 6, 10, 15]
- 출력
- true
- 설명
- 각 노드는 자신보다 위에 있는 모든 노드의 올바른 쪽에 있습니다. 순서대로(왼쪽 하위 트리, 노드, 오른쪽 하위 트리) 읽으면 값은
1, 3, 6, 8, 10, 12, 15로 나오며, 엄격히 증가합니다. 이것이 탐색 트리가 제공하는 것입니다.
- 입력
- tree = [10, 5, 15, -1, -1, 6, 20]
- 출력
- false
- 설명
- 모든 노드는 왼쪽 자식보다 크고 오른쪽 자식보다 작지만, 트리는 유효하지 않습니다. 인덱스
5에 있는6은 루트10의 오른쪽 서브트리에 있으므로10보다 커야 하지만, 그렇지 않습니다.
- 입력
- tree = [12, 7, 12]
- 출력
- false
- 설명
- 루트의 오른쪽 자식은 루트와 같은 값인
12를 갖습니다. 오른쪽 하위 트리의 값은 반드시 더 커야 하므로, 같은 값이면 규칙을 위반합니다.
제출 시 숨은 테스트 +16개
후속 질문
인덱스 i에 있는 노드의 부모는 (i-1)/2에 있으며, 소수점 이하는 버립니다. 스택을 유지하거나 재귀하는 대신 부모를 따라 이동하면서 O(1)의 추가 공간으로 트리를 순회할 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
[10, 5, 15, -1, -1, 6, 20]에서 모든 노드는 왼쪽 자식보다 크고 오른쪽 자식보다 작습니다. 그런데도 왜 검색 트리가 아닌가요?모든 조상 노드는 해당 노드에 제한을 둡니다. 해당 노드가 왼쪽에 있으면 조상 노드보다 작아야 하고, 오른쪽에 있으면 커야 합니다. 이러한 제한을 모두 합치면 하나의 열린 구간이 됩니다. 값
v에서 왼쪽으로 이동하면 상한이v로 낮아지고, 오른쪽으로 이동하면 하한이v로 높아집니다.(index, low, high)의 스택을 유지하고, 루트와 모든 허용 값보다 넓은 범위로 시작합니다. 항목을 꺼내 값이 범위 안에 엄격하게 포함되지 않으면 실패 처리하고, 실제 자식마다 범위가 좁혀진 항목을 스택에 넣습니다.
풀이
이 규칙은 노드와 그 두 자식이 아니라 전체 하위 트리에 관한 것입니다. 트리의 모든 노드에서 부모와 자식 검사를 통과하더라도 여전히 잘못된 트리일 수 있습니다. 깊은 곳에 있는 노드가 여러 단계 위 조상이 정한 제한을 어길 수 있기 때문입니다. 이 문제를 깔끔하게 처리하는 방법은 두 가지입니다. 트리를 순서대로 읽으며 값이 엄격하게 증가하는지 확인하거나, 각 노드에 조상이 허용하는 값의 범위를 전달하고 해당 노드가 그 범위에 속하는지 확인하는 것입니다.
각 노드를 전체 하위 트리와 비교합니다
핵심 아이디어
먼저 배열에서 노드를 탐색하는 방법을 살펴봅시다. 인덱스 i에 있는 노드의 왼쪽 자식은 2*i+1에, 오른쪽 자식은 2*i+2에 있습니다. 자식은 해당 인덱스가 배열 안에 있고 그 위치의 값이 -1이 아닌 경우에만 실제로 존재합니다. [10, 5, 15, -1, -1, 6, 20]에서 루트 10의 인덱스 1과 2에는 5와 15가 있고, 15의 인덱스 5와 6에는 6과 20이 있습니다.
대부분의 사람이 처음 시도하는 방법은 각 노드를 양쪽 자식과만 비교하는 것입니다. 이 트리는 그 방법이 실패하는 이유를 보여 줍니다. 5 < 10, 15 > 10, 6 < 15, 20 > 15는 모두 성립하지만, 6은 10의 오른쪽에 있습니다. 정의는 하위 트리에 있는 모든 값을 대상으로 하므로, 바로 그 조건을 확인하세요.
v를 값으로 가지는 노드에서 왼쪽의 모든 값이 v보다 작으려면 왼쪽에서 가장 큰 값이 v보다 작으면 됩니다. 마찬가지로 오른쪽의 모든 값이 v보다 크려면 그쪽에서 가장 작은 값이 v보다 크면 됩니다. 간단한 재귀 헬퍼 함수 두 개로 각각 가장 큰 값과 가장 작은 값을 찾습니다. 비어 있는 쪽에서는 가장 큰 값을 -1, 가장 작은 값을 100001로 둡니다. 이 값들은 허용 범위 밖에 있으므로 비어 있는 쪽에서는 조건이 실패하지 않습니다.
이 방법은 올바르지만 작업이 반복됩니다. 각 노드는 위쪽에 있는 조상마다 한 번씩 탐색되므로, 깊이가 h인 트리의 총 방문 횟수는 대략 n × h입니다. 깊이가 최대 14인 경우에는 여기서 문제가 없지만, n개의 노드가 하나의 긴 경로를 이루는 트리에서는 O(n²)까지 늘어납니다.
알고리즘
- 값이
-1이 아닌 모든 인덱스i를 확인합니다. 2*i+1에서 시작하는 왼쪽 하위 트리에서 가장 큰 값을 찾거나, 해당 위치가 비어 있으면-1을 사용합니다.2*i+2에서 시작하는 오른쪽 하위 트리에서 가장 작은 값을 찾거나, 해당 위치가 비어 있으면100001을 사용합니다.- 가장 큰 값이
tree[i]보다 크거나 같거나, 가장 작은 값이tree[i]보다 작거나 같으면false를 반환합니다. - 마지막 노드까지 확인한 후
true를 반환합니다.
def isValidBST(tree):
n = len(tree)
def largest(i):
# Largest value in the subtree at index i, or -1 when that spot is empty.
if i >= n or tree[i] == -1:
return -1
return max(tree[i], largest(2 * i + 1), largest(2 * i + 2))
def smallest(i):
# Smallest value in the subtree at index i, or 100001 when that spot is empty.
if i >= n or tree[i] == -1:
return 100001
return min(tree[i], smallest(2 * i + 1), smallest(2 * i + 2))
for i in range(n):
if tree[i] == -1:
continue
# Everything on the left must be smaller, everything on the right larger.
if largest(2 * i + 1) >= tree[i] or smallest(2 * i + 2) <= tree[i]:
return False
return True중위 순회 값은 반드시 엄격히 증가해야 합니다
핵심 아이디어
중위 순회는 왼쪽 하위 트리, 노드, 오른쪽 하위 트리 순서로 방문합니다. 이진 탐색 트리에서는 그 순서대로 값이 정렬됩니다. 왼쪽의 모든 값은 더 작으므로 먼저 오고, 오른쪽의 모든 값은 더 크므로 나중에 옵니다. 첫 번째 예시는 1, 3, 6, 8, 10, 12, 15로 읽힙니다.
역도 성립하며, 이것이 이 검사가 가능한 이유입니다. 임의의 노드 v를 보겠습니다. 중위 순회 순서에서 해당 노드의 왼쪽 하위 트리 전체는 바로 앞에, 오른쪽 하위 트리 전체는 바로 뒤에 놓입니다. 순서가 엄격히 증가한다면 v 앞의 모든 값은 더 작고 뒤의 모든 값은 더 크므로, v에서 이 규칙이 성립하며 다른 모든 노드에서도 마찬가지입니다.
따라서 트리를 중위 순회하며 값을 모은 다음, 각 값을 바로 앞의 값과 비교하면 됩니다. 두 번째 예시는 5, 10, 6, 15, 20으로 읽힙니다. 10에서 6으로 내려가는 단계에서 잘못된 쪽에 있는 노드가 드러납니다. 세 번째 예시는 7, 12, 12로 읽히며, 반복된 12가 엄격한 검사를 통과하지 못합니다. 각 노드는 한 번씩 방문하므로 시간은 O(n)이고, 목록에는 O(n)의 공간이 필요합니다.
알고리즘
walk(i)를 작성합니다. 위치가 비어 있으면 중단하고, 그렇지 않으면2*i+1을 순회하고tree[i]를 추가한 다음2*i+2를 순회합니다.- 값을 순서대로 수집하려면
walk(0)을 호출합니다. 1부터 각 위치k에 대해values[k-1] ≥ values[k]이면false를 반환합니다.true를 반환합니다.
def isValidBST(tree):
n = len(tree)
values = []
def walk(i):
# Left subtree, then the node, then the right subtree.
if i >= n or tree[i] == -1:
return
walk(2 * i + 1)
values.append(tree[i])
walk(2 * i + 2)
walk(0)
# A search tree read in order gives strictly increasing values.
for k in range(1, len(values)):
if values[k - 1] >= values[k]:
return False
return True허용 범위를 트리 아래로 전달하세요
핵심 아이디어
노드의 관점에서 규칙을 살펴보세요. 모든 조상은 해당 노드에 하나의 제한을 둡니다. 노드가 a를 가진 조상의 왼쪽 하위 트리에 있으면 그 값은 a보다 작아야 하고, 오른쪽 하위 트리에 있으면 a보다 커야 합니다. 이 모든 제한을 합치면 하나의 열린 범위 (low, high)가 되며, 노드의 값이 이 범위 안에 엄격히 들어갈 때만 올바른 위치에 있는 것입니다.
내려가는 동안 이 범위를 만들 수 있습니다. 루트에는 제한이 없습니다. v를 가진 노드에서 왼쪽 자식으로 이동하면 low는 유지하고 high를 v로 낮춥니다. 오른쪽 자식으로 이동하면 high는 유지하고 low를 v로 높입니다. 새로운 제한은 대체하는 기존 제한보다 항상 더 엄격합니다. v 자체가 기존 범위에 대한 검사를 통과했기 때문입니다.
두 번째 예시에서 15는 범위 (10, no limit)를 받고, 이를 왼쪽 자식에게 (10, 15)로 전달합니다. 6은 10보다 작으므로 다른 노드를 살펴보지 않고 바로 여기서 검사가 실패합니다. 값의 범위가 0부터 10^5까지이므로 -1과 100001을 "제한 없음"을 나타내는 값으로 사용할 수 있습니다.
범위와 함께 아직 처리할 노드들을 스택에 보관하세요. 각 노드는 한 번씩 검사하므로 시간 복잡도는 O(n)이고, 스택에는 한 경로에 있는 처리 대기 노드들이 저장되므로 공간 복잡도는 O(h)입니다. 처음 범위가 깨지는 지점에서 탐색을 끝냅니다.
알고리즘
(0, -1, 100001)을 푸시합니다. 루트의 인덱스와 실제 제한이 없는 열린 범위입니다.(i, low, high)를 팝합니다.tree[i]가low와high사이에 엄격히 있지 않으면false를 반환합니다.- 왼쪽 자식
2*i+1이 실제로 존재하면 범위(low, tree[i])와 함께 푸시합니다. - 오른쪽 자식
2*i+2가 실제로 존재하면 범위(tree[i], high)와 함께 푸시합니다. - 스택이 비어 있으면
true를 반환합니다.
def isValidBST(tree):
n = len(tree)
# Each entry: a node index and the open range (low, high) its value must fall in.
# -1 and 100001 lie outside every allowed value, so they mean "no limit".
stack = [(0, -1, 100001)]
while stack:
i, low, high = stack.pop()
value = tree[i]
if not (low < value < high):
return False
left, right = 2 * i + 1, 2 * i + 2
if left < n and tree[left] != -1:
stack.append((left, low, value)) # the left side must stay below value
if right < n and tree[right] != -1:
stack.append((right, value, high)) # the right side must stay above value
return True
함정과 경계 사례
대부분의 오답은 확인을 너무 적게 하거나, 올바른 대상을 잘못된 비교 방식으로 확인합니다.
- 노드를 자식과만 비교합니다.
[10, 5, 15, -1, -1, 6, 20]에서는 모든 부모-자식 쌍이 올바르게 보이지만,6은 여전히 두 단계 위에 있는 루트가 정한 범위를 벗어납니다. - 같은 값을 허용합니다. 양쪽의 순서는 모두 엄격해야 하므로
[12, 7, 12]는 유효하지 않습니다.low < v < high와values[k-1] < values[k]를 사용하고,≤는 절대 사용하지 마세요. - 부모의 값만 아래로 전달합니다. 왼쪽 자식에는 두 가지 제한이 모두 필요합니다. 부모보다 작아야 하고, 부모가 가지고 있던 하한보다 커야 합니다. 전체 범위를 전달하세요.
- 노드에 들어갈 수 있는 값을 '제한 없음' 값으로 선택합니다. 값은
0부터 시작하므로 하한이0이면[0]처럼0을 가진 유효한 노드를 거부하게 됩니다. 허용되는 모든 값보다 작은 값에서 시작하세요. - 배열의 끝을 넘어 읽습니다. 자식을 읽기 전에
2*i+1 < tree.length인지 확인하고,-1은 자식이 없음을 나타내는 것으로 처리하세요. - 배열 인덱스가 1부터 시작하는 Lua와 R에서 오프셋을 혼동합니다.
2*i+1계산을 위해 노드 인덱스는 0부터 시작하도록 유지하고,tree[i + 1]을 읽으세요.
자주 묻는 질문4
각 노드를 자식 노드와 비교하는 것만으로는 왜 BST가 유효한지 확인하기에 충분하지 않을까요?
이 규칙은 전체 하위 트리에 적용됩니다. 루트의 오른쪽 하위 트리 깊숙이 있는 노드는 훨씬 큰 노드의 왼쪽 자식이더라도 루트보다 커야 합니다. [10, 5, 15, -1, -1, 6, 20]에서 6은 15의 왼쪽 자식으로는 적절하지만 10의 오른쪽에 있으므로, 이 트리는 탐색 트리가 아닙니다. 부모뿐 아니라 모든 조상의 제한값이 필요합니다.
이진 탐색 트리를 검증하는 시간 복잡도는 얼마인가요?
표준적인 두 가지 방법인 중위 순회 검사와 범위 검사는 각 노드를 한 번씩 확인하므로 O(n) 시간이 걸립니다. 범위 검사는 스택을 위해 O(h)의 추가 공간이 필요하며, 여기서 h는 깊이입니다. 각 노드를 전체 하위 트리의 모든 노드와 비교하는 방법도 가능하지만 O(n × h)의 비용이 들며, 경로 모양의 트리에서는 O(n²)에 이릅니다.
모든 값을 저장하지 않고 중위 순회로 BST가 유효한지 확인할 수 있나요?
네. 중위 순회 검사는 값과 바로 앞의 값만 비교하므로, 목록 대신 변수에 이전 값을 저장하세요. 재귀나 명시적 스택을 사용해 트리를 중위 순회하고, 값이 이전 값보다 크지 않은 순간 false를 반환하세요. 그러면 추가 공간이 O(h)로 줄어듭니다.
이진 검색 트리에 중복된 값이 들어갈 수 있나요?
여기서 사용하는 엄격한 정의에서는 그렇지 않습니다. 왼쪽의 모든 값은 더 작아야 하고 오른쪽의 모든 값은 더 커야 하므로, 같은 두 값이 둘 다 조건을 만족할 수는 없습니다. 일부 교과서에서는 중복 값을 한쪽에 허용합니다. 예를 들어 같은 값을 오른쪽에 둘 수 있습니다. 그 규칙을 따르면 엄격한 비교 하나를 ≤로 바꾸면 되므로, 검사를 작성하기 전에 정의를 읽어 보세요.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def isValidBST(tree):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
tree = [8, 3, 12, 1, 6, 10, 15]
기대값
true