Range Sum of BST

Q: BST 범위 합의 시간 복잡도는 얼마인가요?

검색 트리의 순서를 활용해 가지치기하는 순회는 범위에 속하는 k 개의 노드와 루트에서 뻗는 최대 두 개의 경로에 있는 노드들을 방문하므로, 깊이가 h 인 트리에서 시간 복잡도는 O(h + k) 입니다. 최악의 경우, 모든 값이 범위에 속하면 O(n) 입니다. 추가 공간 복잡도는 스택 또는 재귀 호출에 필요한 O(h) 입니다.

Q: BST의 범위 합에서 하위 트리를 건너뛸 수 있는 이유는 무엇인가요?

이진 탐색 트리에서는 노드의 왼쪽에 있는 모든 값이 노드보다 작고, 오른쪽에 있는 모든 값이 노드보다 큽니다. 노드의 값이 low 이하라면 왼쪽에 있는 값 중 범위에 포함되는 값은 없고, high 이상이라면 오른쪽에 있는 값 중 범위에 포함되는 값은 없습니다. 해당 방향을 건너뛰어도 범위에 포함되는 값을 놓치지 않습니다.

Q: BST의 범위 합을 중위 순회로 해결할 수 있을까요?

맞습니다. 이진 탐색 트리를 중위 순회하면 값이 오름차순으로 나열되므로, low 에 도달한 값을 더하고 high 를 넘는 값이 나오면 바로 멈출 수 있습니다. 같은 답을 얻을 수 있으며, 조기 종료는 트리의 오른쪽에서 작업을 줄여 주고, 가지치기 검색은 왼쪽에서 작업을 줄여 줍니다.

Q: BST의 범위 합을 구할 때 재귀를 사용해야 할까요, 아니면 스택을 사용해야 할까요?

둘 다 작동합니다. 재귀 방식은 더 짧고, 여기서는 깊이가 최대 14이므로 호출 스택도 작게 유지됩니다. 명시적인 스택을 사용하면 재귀 제한을 완전히 피할 수 있습니다. 이는 수천 개의 레벨로 이루어진 높이가 큰 트리에서 중요하며, 이 페이지의 풀이에서 사용하는 방식이기도 합니다.

쉬움이진 탐색 트리 트리 순회

+10

레벨 순서로 배열 tree에 저장된 이진 탐색 트리와 두 숫자 low 및 high가 주어집니다. 루트는 인덱스 0에 있고, 인덱스 i에 있는 노드의 자식은 2*i+1(왼쪽)과 2*i+2(오른쪽)에 있으며, -1은 비어 있는 위치를 나타내고, 배열은 끝에 추가 -1 항목이 올 수 있습니다. 이진 탐색 트리에서는 노드의 왼쪽 하위 트리에 있는 모든 값이 노드의 값보다 작고, 오른쪽 하위 트리에 있는 모든 값은 더 큽니다.

rangeSumBST라는 함수를 작성하여 low ≤ v ≤ high를 만족하는 모든 노드 값 v의 합을 반환하세요. 해당 범위에 값이 없으면 0을 반환합니다.

함수

rangeSumBST(tree: integer-array, low: integer, high: integer) → integer

treeinteger-array: 이진 탐색 트리를 레벨 순서대로 나열하고, 빈 위치에는 -1을 사용합니다
lowinteger: 개수를 세기 위한 최솟값
highinteger: 계산할 가장 큰 값
반환값integer: low와 high 사이의 노드 값의 합(양 끝값 포함)

제약 조건

1 ≤ tree.length ≤ 32767
각 tree[i]는 -1이거나 0 ≤ tree[i] ≤ 10⁵인 값입니다.
tree[0]은 절대 -1이 아니므로 트리에는 노드가 적어도 하나 있습니다.
배열은 마지막 노드 뒤에 추가적인 -1 항목이 올 수 있습니다.
빈 자리의 두 자식도 모두 비어 있으며, 깊이는 최대 14입니다.
이 트리는 유효한 이진 탐색 트리이므로 모든 값이 서로 다릅니다.
0 ≤ low ≤ high ≤ 10⁵
답은 32비트 부호 있는 정수 범위에 들어갑니다.

예제

입력: tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
출력: 88
설명: 9부터 31까지의 값은 10, 12, 15, 20, 31이며, 합하면 88입니다. 3, 8, 40은 범위에 포함되지 않습니다.

입력: tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
출력: 0
설명: 트리에는 25, 50, 75가 있으며, 그중 어느 것도 60과 70 사이에 있지 않으므로 합계는 0입니다. 네 개의 -1 항목은 25와 75의 비어 있는 자식 위치입니다.

입력: tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
출력: 4
설명: low와 high가 모두 4이므로, 값이 4인 노드만 계산됩니다. 인덱스 4에 있는 4는 2의 오른쪽 자식이므로 답은 4입니다.

제출 시 숨은 테스트 +14개

후속 질문

같은 트리에서 서로 다른 (low, high) 쿼리 수천 개에 답해야 한다면, 각 쿼리에 O(log n) 시간 안에 어떻게 답할 수 있을까요?

힌트

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

3개 중 0개 열림

풀이

범위에 있는 모든 값을 더하는 것은 단순한 순회입니다. 각 노드를 방문하고 조건에 맞는 값만 남기면 됩니다. 이진 탐색 트리의 순서를 이용하면 더 효율적으로 처리할 수 있습니다. 노드의 값은 더 작은 값과 더 큰 값이 어느 쪽에 있는지 알려 주므로, 하위 트리 안의 노드를 하나도 살펴보지 않고도 하위 트리 전체를 건너뛸 수 있습니다.

모든 노드를 방문하세요

핵심 아이디어

먼저 배열에서 이동하는 방법을 살펴보겠습니다. 인덱스 i에 있는 노드의 왼쪽 자식은 2*i+1에, 오른쪽 자식은 2*i+2에 있습니다. 자식은 해당 인덱스가 배열 안에 있고 그 위치의 값이 -1이 아닐 때만 실제로 존재합니다. [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]에서 루트 20의 8과 31은 인덱스 1과 2에 있고, 인덱스 4의 12의 10과 15는 인덱스 9와 10에 있으며, 31의 왼쪽 자리는 인덱스 5에서 비어 있습니다.

이제 핵심 아이디어를 살펴보겠습니다. 범위 안의 모든 값은 어떤 노드에 있으므로, 모든 노드에 도달해 low ≤ v ≤ high인 값들을 더하는 순회를 하면 올바른 합계를 얻을 수 있습니다. 노드 인덱스를 저장할 스택을 사용하세요. 루트에서 시작해 인덱스를 하나 꺼내고, 그 값이 범위 안에 있으면 더한 다음, 실제로 존재하는 자식들을 각각 스택에 넣습니다.

이 방법은 이진 탐색 트리의 속성을 전혀 활용하지 않으며, 어떤 이진 트리에서든 작동합니다. n개의 노드를 모두 방문하므로 시간 복잡도는 O(n)이고, 스택에는 한 경로를 따라 처리해야 할 자식들이 저장되므로 깊이가 h일 때 공간 복잡도는 O(h)입니다. 수천 개의 노드가 있는 트리에서 범위가 값 몇 개만 포함한다면, 대부분의 작업이 낭비됩니다.

알고리즘

루트 인덱스 0을 스택에 넣고 total = 0으로 설정합니다.
인덱스 i를 꺼냅니다. low ≤ tree[i] ≤ high이면 tree[i]를 total에 더합니다.
배열 범위 안에 있고 -1이 아닌 경우 2*i+1과 2*i+2를 넣습니다.
스택이 비면 total을 반환합니다.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and tree[left] != -1:
            stack.append(left)
        if right < n and tree[right] != -1:
            stack.append(right)
    return total

이진 탐색 트리 순서로 가지치기

핵심 아이디어

같은 스택 순회를 유지하되, 순서를 이용하세요. 노드에 v가 있다고 해 봅시다. 왼쪽 하위 트리에는 v보다 작은 값만 있습니다. v ≤ low이면 왼쪽 하위 트리의 모든 값이 low보다 작으므로 왼쪽 하위 트리에서는 추가할 값이 없습니다. 따라서 건너뜁니다. 마찬가지로 v ≥ high이면 오른쪽 하위 트리에는 high보다 큰 값만 있으므로 건너뜁니다. 따라서 v > low일 때만 왼쪽 자식을, v < high일 때만 오른쪽 자식을 스택에 넣습니다.

범위가 [9, 31]인 첫 번째 예에서 31은 high와 같으므로 오른쪽 자식인 40은 스택에 들어가지 않습니다. 8은 low보다 작으므로 왼쪽 자식인 3은 건너뛰지만, 오른쪽 자식인 12는 계속 방문합니다. 8과 20 사이의 값은 범위에 포함될 수 있기 때문입니다.

방문하는 노드는 범위 안에 있는 k개의 값과, 범위의 경계를 따라가는 루트에서 잎까지의 경로 최대 두 개이므로 시간 복잡도는 O(h + k)입니다. 범위가 트리 전체를 포함하면 여전히 O(n)이지만, 큰 트리에서 좁은 범위를 지정하면 수십 개의 노드만 방문합니다. 스택은 O(h) 공간을 사용합니다.

알고리즘

루트 인덱스 0을 스택에 넣고 total = 0으로 설정합니다.
인덱스 i를 꺼내 v = tree[i]를 읽습니다. low ≤ v ≤ high이면 v를 total에 더합니다.
v > low이면 왼쪽 자식 2*i+1이 실제로 존재할 때 스택에 넣습니다.
v < high이면 오른쪽 자식 2*i+2가 실제로 존재할 때 스택에 넣습니다.
스택이 비면 total을 반환합니다.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        # Smaller values sit on the left, larger on the right: skip a side the range cannot reach.
        if value > low and left < n and tree[left] != -1:
            stack.append(left)
        if value < high and right < n and tree[right] != -1:
            stack.append(right)
    return total

함정과 경계 사례

대부분의 오답은 범위나 배열의 경계에서 발생합니다.

엄격한 비교를 사용합니다. 양쪽 끝이 모두 포함되므로 low 또는 high와 같은 노드도 셉니다.
가지치기를 너무 일찍 합니다. v가 low와 같으면 왼쪽 하위 트리를 건너뛸 수 있지만, v가 low + 1이면 건너뛸 수 없습니다. 왼쪽 하위 트리에 low 자체가 있을 수 있기 때문입니다.
범위 밖의 노드에서 탐색을 멈춥니다. low보다 작은 노드라도 범위 안의 값으로 가득 찬 오른쪽 하위 트리를 가질 수 있으므로, 순서 규칙상 제외되는 쪽만 건너뛰세요.
배열의 끝을 넘어 자식 인덱스를 읽습니다. 값을 읽기 전에 2*i+1 < tree.length인지 확인하고, -1은 자식이 없는 것으로 처리하세요.
배열 인덱스가 1부터 시작하는 Lua와 R에서 오프셋을 혼동합니다. 2*i+1 계산을 위해 노드 인덱스는 0부터 시작하도록 유지하고, tree[i + 1]을 읽으세요.

자주 묻는 질문4

BST 범위 합의 시간 복잡도는 얼마인가요?

검색 트리의 순서를 활용해 가지치기하는 순회는 범위에 속하는 k개의 노드와 루트에서 뻗는 최대 두 개의 경로에 있는 노드들을 방문하므로, 깊이가 h인 트리에서 시간 복잡도는 O(h + k)입니다. 최악의 경우, 모든 값이 범위에 속하면 O(n)입니다. 추가 공간 복잡도는 스택 또는 재귀 호출에 필요한 O(h)입니다.

BST의 범위 합에서 하위 트리를 건너뛸 수 있는 이유는 무엇인가요?

이진 탐색 트리에서는 노드의 왼쪽에 있는 모든 값이 노드보다 작고, 오른쪽에 있는 모든 값이 노드보다 큽니다. 노드의 값이 low 이하라면 왼쪽에 있는 값 중 범위에 포함되는 값은 없고, high 이상이라면 오른쪽에 있는 값 중 범위에 포함되는 값은 없습니다. 해당 방향을 건너뛰어도 범위에 포함되는 값을 놓치지 않습니다.

BST의 범위 합을 중위 순회로 해결할 수 있을까요?

맞습니다. 이진 탐색 트리를 중위 순회하면 값이 오름차순으로 나열되므로, low에 도달한 값을 더하고 high를 넘는 값이 나오면 바로 멈출 수 있습니다. 같은 답을 얻을 수 있으며, 조기 종료는 트리의 오른쪽에서 작업을 줄여 주고, 가지치기 검색은 왼쪽에서 작업을 줄여 줍니다.

BST의 범위 합을 구할 때 재귀를 사용해야 할까요, 아니면 스택을 사용해야 할까요?

둘 다 작동합니다. 재귀 방식은 더 짧고, 여기서는 깊이가 최대 14이므로 호출 스택도 작게 유지됩니다. 명시적인 스택을 사용하면 재귀 제한을 완전히 피할 수 있습니다. 이는 수천 개의 레벨로 이루어진 높이가 큰 트리에서 중요하며, 이 페이지의 풀이에서 사용하는 방식이기도 합니다.

Python

def rangeSumBST(tree, low, high):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]
low = 9
high = 31

기대값