Validate Binary Search Tree

Q: 이진 탐색 트리의 유효성을 검사하는 시간 복잡도는 얼마인가요?

중위 순회 검사와 범위 검사는 각 노드를 한 번씩 방문합니다. 즉, 시간은 O(n) 이고, 깊이가 h 인 트리에서 범위 검사의 스택에 필요한 추가 공간은 O(h) 입니다. 모든 노드를 그 노드의 전체 하위 트리와 비교하면 O(n × h) 의 비용이 들며, 경로 모양의 트리에서는 O(n²) 에 이릅니다.

Q: 모든 값을 저장하지 않고 중위 순회로 BST가 유효한지 확인할 수 있나요?

맞습니다. 검사는 각 값을 바로 앞의 값과만 비교하므로, 목록 대신 변수에 이전 값을 저장하고 값이 더 크지 않은 순간 false 를 반환하세요. 추가 공간은 재귀 또는 스택에 대해 O(h) 로 줄어듭니다.

Q: 이진 검색 트리에 중복된 값이 포함될 수 있나요?

여기서 사용되는 엄격한 정의에 따르면 아닙니다. 같은 값은 어느 쪽에도 들어갈 수 없습니다. 일부 교재에서는 예를 들어 오른쪽처럼 한쪽에 같은 값을 허용합니다. 그 규칙에서는 엄격한 비교 연산자 하나가 ≤ 가 됩니다.

보통이진 탐색 트리 트리 순회

+10

이진 트리는 힙 순서로 배열 tree에 저장됩니다. 루트는 인덱스 0에 있고, 인덱스 i의 자식은 2*i+1(왼쪽)과 2*i+2(오른쪽)에 있습니다. -1은 비어 있는 위치를 나타내며, 배열 끝에 여분의 -1 항목이 있을 수 있습니다.

이진 탐색 트리이면 true를, 그렇지 않으면 false를 반환하는 isValidBST를 작성하세요. 이진 탐색 트리에서는 각 노드의 값이 왼쪽 하위 트리의 모든 값보다 엄격히 크고 오른쪽 하위 트리의 모든 값보다 엄격히 작습니다.

함수

isValidBST(tree: integer-array) → boolean

treeinteger-array: 빈 위치는 -1로 표시하는 레벨 순서의 이진 트리
반환값boolean: 트리가 이진 검색 트리이면 true, 그렇지 않으면 false

제약 조건

1 ≤ tree.length ≤ 32767
각 tree[i]는 -1이거나 0 ≤ tree[i] ≤ 10⁵를 만족하는 값입니다.
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보다 커야 합니다.

입력: tree = [12, 7, 12]
출력: false
설명: 루트의 오른쪽 자식은 루트와 같은 12를 갖습니다. 오른쪽 하위 트리는 엄격히 더 커야 하므로 이 트리는 조건을 충족하지 못합니다.

후속 질문

A node의 부모는 인덱스 (i-1)/2에 있으며, 내림합니다. 스택이나 재귀 대신 부모를 따라 이동하면서 추가 공간 O(1)로 트리를 중위 순회할 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

이 규칙은 전체 하위 트리에 적용되므로, 각 노드를 두 자식과 비교하는 것만으로는 충분하지 않습니다. 깊숙이 있는 노드가 여러 단계 위 조상이 설정한 한계를 어길 수 있기 때문입니다. 트리를 중위 순회하며 값이 엄격하게 증가하는지 확인하거나, 각 노드에 조상들이 허용하는 범위를 전달하세요.

각 노드를 전체 하위 트리와 비교합니다

핵심 아이디어

노드의 왼쪽에 있는 모든 값이 값 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

중위 순회 값은 반드시 엄격하게 증가해야 합니다

핵심 아이디어

중위 순회는 왼쪽 하위 트리, 노드, 오른쪽 하위 트리 순서로 방문하므로, 이진 탐색 트리에서는 값을 정렬된 순서로 읽습니다.

그 역도 성립합니다. 임의의 노드 v에 대해 왼쪽 하위 트리 전체는 순서에서 그 노드 바로 앞에 오고, 오른쪽 하위 트리 전체는 바로 뒤에 옵니다. 순서가 엄격히 증가한다면 v보다 앞에 있는 모든 값은 더 작고 뒤에 있는 모든 값은 더 크므로, 이 규칙은 v에서 성립하며 다른 모든 노드에서도 마찬가지로 성립합니다.

두 번째 예제는 5, 10, 6, 15, 20을 읽습니다. 10에서 6으로의 하락이 잘못 배치된 노드를 드러냅니다. 각 노드는 한 번씩 방문합니다. 시간 복잡도는 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)이 되며, 노드의 값이 그 안에 엄격히 들어갈 때만 노드가 올바른 위치에 있습니다.

내려가면서 구간을 만듭니다. 왼쪽 자식은 low를 유지하고 high = v를 받습니다. 오른쪽 자식은 high를 유지하고 low = v를 받습니다. 두 번째 예에서 15는 왼쪽 자식에게 (10, 15)를 전달하고, 6은 즉시 실패합니다. 값은 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]는 유효하지 않습니다. <와 비교하고, 절대로 ≤와 비교하지 마세요.
하한 "제한 없음" 값으로 0을 사용하는 것. 유효한 트리 [0]을 거부합니다.
2*i+1 < tree.length인지 확인하지 않고 자식을 읽는 것. [12, 7, 12]에서 인덱스 3은 끝을 벗어납니다.
Lua와 R에서는 배열이 1부터 시작합니다. 2*i+1에 사용할 노드 인덱스는 0부터 시작하도록 유지하고, tree[i + 1]을 읽으세요.

자주 묻는 질문3

이진 탐색 트리의 유효성을 검사하는 시간 복잡도는 얼마인가요?

중위 순회 검사와 범위 검사는 각 노드를 한 번씩 방문합니다. 즉, 시간은 O(n)이고, 깊이가 h인 트리에서 범위 검사의 스택에 필요한 추가 공간은 O(h)입니다. 모든 노드를 그 노드의 전체 하위 트리와 비교하면 O(n × h)의 비용이 들며, 경로 모양의 트리에서는 O(n²)에 이릅니다.

모든 값을 저장하지 않고 중위 순회로 BST가 유효한지 확인할 수 있나요?

맞습니다. 검사는 각 값을 바로 앞의 값과만 비교하므로, 목록 대신 변수에 이전 값을 저장하고 값이 더 크지 않은 순간 false를 반환하세요. 추가 공간은 재귀 또는 스택에 대해 O(h)로 줄어듭니다.

이진 검색 트리에 중복된 값이 포함될 수 있나요?

여기서 사용되는 엄격한 정의에 따르면 아닙니다. 같은 값은 어느 쪽에도 들어갈 수 없습니다. 일부 교재에서는 예를 들어 오른쪽처럼 한쪽에 같은 값을 허용합니다. 그 규칙에서는 엄격한 비교 연산자 하나가 ≤가 됩니다.

def isValidBST(tree):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

tree = [8, 3, 12, 1, 6, 10, 15]

예상 출력

true

Validate Binary Search Tree

함수

제약 조건

예제

힌트

풀이

각 노드를 전체 하위 트리와 비교합니다

중위 순회 값은 반드시 엄격하게 증가해야 합니다

허용 범위를 트리 아래로 전달합니다

함정과 경계 사례

자주 묻는 질문3

비슷한 문제