Kth Smallest Element in a BST
힙 순서의 배열 root로 이진 탐색 트리가 주어집니다. 루트는 인덱스 0에 있고, 인덱스 i의 자식은 2*i+1(왼쪽)과 2*i+2(오른쪽)에 있으며, -1은 빈 위치를 나타냅니다. 배열 끝에 추가적인 -1 항목이 있을 수 있습니다. 각 노드에서 왼쪽 서브트리에는 더 작은 값만 있고 오른쪽 서브트리에는 더 큰 값만 있습니다.
트리에서 1부터 세었을 때 k번째로 작은 값을 반환하세요.
함수
- rootinteger-array
- 빈 위치에는 -1을 사용한 이진 탐색 트리의 레벨 순서
- kinteger
- 오름차순으로 찾을 위치(1부터 시작)
- 반환값integer
- 트리에서 k번째로 작은 값
제약 조건
1 ≤ root.length ≤ 32767- 각
root[i]는-1이거나0 ≤ root[i] ≤ 105를 만족하는 값입니다. root[0]은 절대-1이 아니므로 트리에는 노드가 하나 이상 있습니다.- 배열은 마지막 노드 뒤에 추가
-1항목을 포함할 수 있습니다. - 빈 자리의 두 자식도 모두 비어 있으며, 깊이는 최대
14입니다. - 정렬 규칙은 모든 노드에서 성립하므로, 같은 값이 두 번 나타나지 않습니다.
1 ≤ k ≤트리의 노드 수.
예제
- 입력
- root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22]k = 4
- 출력
- 29
- 설명
- 값을 오름차순으로 나열하면
6, 17, 22, 29, 41, 65, 90이고, 네 번째 값은29입니다. 이는 루트의 왼쪽 하위 트리에 있는 네 값 중 가장 큰 값입니다.
- 입력
- root = [12, 5, -1, 2, 9, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1]k = 1
- 출력
- 2
- 설명
- 가장 작은 값은 계속 왼쪽으로 이어지는 경로의 끝에 있습니다:
12,5,2.9아래의7과-1패딩은 이를 바꾸지 않습니다.
후속 질문
트리가 자주 바뀌고 k번째로 작은 값을 여러 번 찾아야 한다면, 모든 질의가 O(h) 시간이 걸리도록 각 노드에 무엇을 저장할 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
이진 탐색 트리를 어떤 방식으로 순회해야 값이 가장 작은 것부터 가장 큰 것까지 나열되나요?
왼쪽 하위 트리, 노드, 오른쪽 하위 트리 순서로 방문하면 정렬된 순서가 됩니다. 이 순회에서
k번째로 나오는 값이 답이므로, 그 지점에서 멈추면 됩니다.스택을 사용하세요. 현재 노드에서 왼쪽 자식으로 이동하면서 노드들을 푸시하세요. 맨 위 항목을 팝하고 개수를 세세요.
k번째 팝에서 멈추세요. 그렇지 않으면 팝한 노드의 오른쪽 자식인2*i+2로 이동해 반복하세요.
풀이
중위 순회(왼쪽 하위 트리, 노드, 오른쪽 하위 트리)는 이진 검색 트리의 값을 오름차순으로 읽으므로, 순회 중 k번째로 도달하는 값이 정답입니다. 직접 스택을 사용해 순회하고 그 지점에서 멈추면 됩니다. 정렬은 필요하지 않습니다.
모든 값을 수집하고 정렬하기
핵심 아이디어
구조는 무시하세요. -1이 아닌 항목을 모두 유지하고 정렬한 다음, 위치 k-1의 값을 반환하세요. 첫 번째 예시에서 정렬된 목록은 6, 17, 22, 29, 41, 65, 90이며, 위치 3에는 29가 있습니다.
순서가 있는 트리든 그렇지 않은 트리든 모두 올바르게 작동합니다. 하지만 여기에는 비용이 따릅니다. 트리에 이미 있는 순서는 무시하고, 정렬에 O(n log n), 복사본을 저장하는 데 O(n)의 메모리를 사용합니다.
알고리즘
-1이 아닌root의 모든 항목을 수집합니다.- 수집한 값을 오름차순으로 정렬합니다.
k-1위치의 값을 반환합니다.
def kthSmallest(root, k):
values = [v for v in root if v != -1] # every node, in any order
values.sort()
return values[k - 1]중위 순회를 리스트로
핵심 아이디어
모든 노드에서 왼쪽 하위 트리에는 더 작은 값만, 오른쪽 하위 트리에는 더 큰 값만 들어 있습니다. 왼쪽 하위 트리, 노드, 오른쪽 하위 트리 순으로 방문하고 각 하위 트리에서도 같은 순서를 따릅니다. 그러면 모든 노드가 더 작은 값 뒤, 더 큰 값 앞에 놓이므로 출력이 정렬됩니다. 첫 번째 예제에서는 순회 결과가 6, 17, 22, 29, 41, 65, 90입니다.
한 번 순회하면 정렬을 대체할 수 있습니다. 시간은 O(n)이고 목록에 필요한 공간은 O(n)입니다. 답이 가장 왼쪽 경로의 끝에 있는 k = 1인 경우에도 트리 전체를 방문합니다.
알고리즘
inorder(i)를 작성하세요. 빈 위치(끝을 지났거나-1)에서는 반환합니다.- 그렇지 않으면
inorder(2*i+1)을 호출하고,root[i]를 목록에 추가한 다음inorder(2*i+2)를 호출합니다. inorder(0)을 호출합니다.- 위치
k-1에 있는 목록 항목을 반환합니다.
def kthSmallest(root, k):
n = len(root)
values = []
def inorder(i):
if i >= n or root[i] == -1:
return
inorder(2 * i + 1) # smaller values first
values.append(root[i])
inorder(2 * i + 2) # then larger ones
inorder(0)
return values[k - 1] # values is sortedk에서 멈추는 반복적 중위 순회
핵심 아이디어
명시적 스택을 사용하면 순회 도중에 멈출 수 있습니다. 가능한 한 왼쪽으로 내려가면서 각 노드를 스택에 넣습니다. 맨 위 노드는 아직 세지 않은 값 중 가장 작습니다. 더 작은 값은 모두 왼쪽 하위 트리에 있고, 그 트리는 비어 있거나 이미 세었기 때문입니다. 노드를 꺼내 세고, 그 노드의 오른쪽 하위 트리가 정렬 순서에서 다음에 옵니다.
첫 번째 예에서 k = 4인 경우: 41, 17, 6을 넣습니다. 6을 꺼낸 다음 17을 꺼내고, 그 오른쪽 자식으로 이동합니다. 29와 22를 넣습니다. 22를 꺼낸 다음, 네 번째 값인 29를 꺼냅니다. 순회는 65나 90에는 전혀 닿지 않습니다.
스택에는 각 레벨당 노드가 최대 하나씩 저장되므로 공간 복잡도는 O(h)입니다. 순회는 한 번 내려간 다음 k번 꺼내므로 시간 복잡도는 O(h + k)입니다.
알고리즘
- 빈 스택과
i = 0으로 시작합니다. i가 실제 노드인 동안i를 푸시하고2*i+1로 이동합니다.- 맨 위의 값을 꺼내
i에 넣고k에서1을 뺍니다. - 이제
k가0이면root[i]를 반환합니다. - 그렇지 않으면
2*i+2로 이동하고 2단계로 돌아갑니다.
def kthSmallest(root, k):
n = len(root)
stack = [] # nodes whose left side is being visited, deepest on top
i = 0
while True:
while i < n and root[i] != -1: # go as far left as you can
stack.append(i)
i = 2 * i + 1
i = stack.pop() # the smallest value not counted yet
k -= 1
if k == 0:
return root[i]
i = 2 * i + 2 # then everything in its right subtree
함정과 경계 사례
- 배열을 인덱스 순서로 읽기. 레벨 순회 결과는 정렬되어 있지 않습니다. 첫 번째 예시는
41, 17, 65로 시작합니다. k에서 off-by-one 오류가 발생합니다.1부터 세므로 목록에서k-1번째 위치를 반환하고, 개수가k에 도달하면 순회를 멈춥니다.- pop한 뒤 오른쪽 하위 트리를 건너뜁니다. 두 번째 예시에서
9와7은5의 오른쪽 하위 트리에 있으므로, 순회 중에 이 값들을 세지 못합니다. - 자식 노드가 없는 경우를 실제 노드로 취급합니다. 자식 노드의 인덱스가 배열 끝을 벗어나거나
-1을 담고 있으면 비어 있는 것입니다.22는 인덱스9에 있으므로, 그 자식인19와20은 배열 끝을 벗어납니다. - Lua와 R의 배열은 1부터 시작합니다.
2*i+1을 위해 노드 인덱스는 0부터 시작하도록 유지하고,root[i + 1]을 읽습니다.
자주 묻는 질문3
BST에서 k번째로 작은 요소를 찾는 시간 복잡도는 얼마인가요?
반복적인 중위 순회는 깊이가 h인 트리에서 O(h + k)의 시간과 O(h)의 추가 공간을 사용합니다. 최악의 경우, k = n이거나 트리가 경로 모양인 경우에는 O(n)입니다.
BST에서 k번째로 큰 요소를 어떻게 찾나요?
순회 순서를 반대로 하세요. 오른쪽 하위 트리, 노드, 왼쪽 하위 트리 순입니다. 그러면 값이 내림차순으로 나열됩니다. 스택에 넣으면서 가능한 한 오른쪽으로 이동하고, 꺼내서 개수를 세고, 꺼낼 때마다 왼쪽 자식으로 이동하세요. k번째로 꺼낸 값이 k번째로 큰 값입니다.
재귀적 중위 순회를 k번째 값에서 어떻게 멈추나요?
재귀 호출 바깥에 k부터 시작하는 카운터를 둡니다. 노드의 왼쪽 하위 트리에서 반환된 후 1을 빼고, 카운터가 0이 되면 노드의 값을 기록합니다. 각 호출이 끝난 후 답이 기록되어 있으면 즉시 반환합니다. 그러면 재귀 방식은 스택 버전과 일치합니다. 시간 복잡도는 O(h + k), 공간 복잡도는 O(h)입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def kthSmallest(root, k):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
인자들
root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22] k = 4
예상 출력
29