Range Sum of BST

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

가지치기된 순회는 범위 내의 k 개 노드와 루트에서 뻗는 최대 두 경로상의 노드를 방문합니다. 깊이가 h 인 트리에서는 O(h + k) 시간이 걸리고, 모든 값이 범위 내에 있을 때는 O(n) 시간이 걸립니다. 스택이나 재귀는 O(h) 공간을 사용합니다.

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

네. 중위 순회는 값을 오름차순으로 나열하므로, 값이 low 에 도달하면 값을 더하고 high 보다 큰 첫 번째 값에서 멈춥니다. 조기 종료는 트리의 오른쪽에서 작업을 줄여 주고, 가지치기는 양쪽에서 작업을 줄여 줍니다.

Q: Range Sum of BST에는 재귀를 사용해야 할까요, 아니면 스택을 사용해야 할까요?

둘 다 작동합니다. 여기서 깊이는 최대 14이므로 재귀가 얕게 유지됩니다. 명시적인 스택을 사용하면 수천 개의 레벨로 이루어진 깊은 트리에서 재귀 한도를 피할 수 있습니다.

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

+10

이진 탐색 트리는 배열 tree에 레벨 순서로 저장됩니다. 루트는 인덱스 0에 있고, 인덱스 i에 있는 노드의 자식은 2*i+1(왼쪽)과 2*i+2(오른쪽)에 있으며, -1은 비어 있는 위치를 나타냅니다. 이진 탐색 트리에서는 노드의 왼쪽 하위 트리에 있는 모든 값이 노드의 값보다 작고, 오른쪽 하위 트리에 있는 모든 값이 노드의 값보다 큽니다.

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입니다.

후속 질문

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

힌트

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

3개 중 0개 열림

풀이

모든 노드를 방문하고 범위 내의 값을 더하는 것은 올바릅니다. 검색 트리의 순서를 활용하면 더 적은 작업으로 처리할 수 있습니다. 노드의 값으로 어느 쪽에 더 작은 값과 더 큰 값이 있는지 알 수 있으므로, 범위에 도달할 수 없는 하위 트리는 열어 보지 않습니다.

모든 노드를 방문하세요

핵심 아이디어

자식은 그 인덱스가 배열 범위 안에 있고 해당 위치의 값이 -1이 아닌 경우에만 실제로 존재합니다. 첫 번째 예에서 인덱스 4의 12에는 인덱스 9와 10에 각각 10과 15가 있고, 인덱스 2의 31에는 인덱스 5의 왼쪽 자리가 비어 있습니다.

범위에 있는 모든 값은 어떤 노드에 들어 있으므로, 모든 노드에 도달해 low ≤ v ≤ high인 값들을 더하는 스택 순회는 올바른 합을 구합니다. 검색 트리의 순서를 무시하므로 범위에 값이 몇 개만 들어 있더라도 n개의 노드를 모두 방문합니다.

알고리즘

루트 인덱스 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이면 그중 범위에 속하는 값이 없으므로 해당 하위 트리를 건너뜁니다. v ≥ high이면 오른쪽 하위 트리에는 high보다 큰 값만 있으므로 그 하위 트리를 건너뜁니다. 첫 번째 예에서 31은 high와 같으므로 오른쪽 자식인 40은 스택에 절대 추가되지 않습니다. 8은 low보다 작으므로 왼쪽 자식인 3은 건너뛰지만, 8과 20 사이의 값은 범위에 속할 수 있으므로 오른쪽 자식인 12는 방문합니다.

범위에 속하는 k개의 값과 루트에서 시작하는 최대 두 경로상의 노드들을 방문합니다. 깊이가 h일 때 시간 복잡도는 O(h + k)입니다. 범위가 트리 전체를 포함하는 경우에도 여전히 O(n)입니다.

알고리즘

루트 인덱스 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 = 4인 세 번째 예시에서는 4를 포함해야 합니다.
너무 이른 단계에서 가지치기하는 경우. v = low에서는 왼쪽 하위 트리를 제외해도 되지만, v = low + 1에서는 그 안에 low 자체가 있을 수 있습니다.
범위를 벗어난 노드의 양쪽 하위 트리를 모두 제외하는 경우. 첫 번째 예시의 8은 low보다 작지만, 그 오른쪽 하위 트리에는 10, 12, 15가 있습니다.
배열의 끝을 넘어 자식 노드를 읽는 경우. 읽기 전에 2*i+1 < tree.length인지 확인하고, -1은 자식이 없음을 나타내는 것으로 처리하세요.
Lua와 R에서는 배열이 1부터 시작합니다. 2*i+1 계산에는 노드 인덱스를 0부터 시작하도록 유지하고, tree[i + 1]을 읽으세요.

자주 묻는 질문3

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

가지치기된 순회는 범위 내의 k개 노드와 루트에서 뻗는 최대 두 경로상의 노드를 방문합니다. 깊이가 h인 트리에서는 O(h + k) 시간이 걸리고, 모든 값이 범위 내에 있을 때는 O(n) 시간이 걸립니다. 스택이나 재귀는 O(h) 공간을 사용합니다.

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

네. 중위 순회는 값을 오름차순으로 나열하므로, 값이 low에 도달하면 값을 더하고 high보다 큰 첫 번째 값에서 멈춥니다. 조기 종료는 트리의 오른쪽에서 작업을 줄여 주고, 가지치기는 양쪽에서 작업을 줄여 줍니다.

Range Sum of BST에는 재귀를 사용해야 할까요, 아니면 스택을 사용해야 할까요?

둘 다 작동합니다. 여기서 깊이는 최대 14이므로 재귀가 얕게 유지됩니다. 명시적인 스택을 사용하면 수천 개의 레벨로 이루어진 깊은 트리에서 재귀 한도를 피할 수 있습니다.

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

테스트 #1

테스트 #2

테스트 #3

인자들

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

예상 출력