Lowest Common Ancestor of a BST
힙 순서로 배열 tree에 저장된 이진 탐색 트리가 주어집니다. 루트는 인덱스 0에 있고, 인덱스 i의 자식은 2*i+1(왼쪽)과 2*i+2(오른쪽)에 있으며, -1은 비어 있는 위치를 나타냅니다. 노드의 왼쪽 하위 트리에 있는 모든 값은 노드의 값보다 작고, 오른쪽 하위 트리에 있는 모든 값은 더 큽니다.
트리에 모두 존재하는 값 p와 q의 가장 낮은 공통 조상의 값을 반환하는 lowestCommonAncestor를 작성하세요. 가장 낮은 공통 조상이란 두 값을 모두 하위 트리에 포함하는 가장 깊은 노드입니다. 노드는 자기 자신의 하위 트리에 포함되므로, p가 q보다 위에 있으면 정답은 p입니다.
함수
- treeinteger-array
- 빈 자리는 -1로 표시한 레벨 순서의 이진 탐색 트리
- pinteger
- 찾을 첫 번째 값
- qinteger
- 찾을 두 번째 값
- 반환값integer
- p와 q를 모두 하위 트리에 포함하는 가장 깊은 노드의 값
제약 조건
1 ≤ tree.length ≤ 32767- 각
tree[i]는-1이거나0 ≤ tree[i] ≤ 105를 만족하는 값입니다. tree[0]은 절대-1이 아니므로 트리에는 노드가 하나 이상 있습니다.- 배열은 마지막 노드 뒤에 추가
-1항목이 올 수 있습니다. - 비어 있는 위치의 두 자식도 비어 있으며, 깊이는 최대
14입니다. - 트리는 유효한 이진 검색 트리이므로 모든 값이 서로 다릅니다.
p와q는 트리의 노드 값입니다. 순서는 임의이며 서로 같을 수도 있습니다.
예제
- 입력
- tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
- 출력
- 8
- 설명
3과15에서 위로 올라가면 두 노드가 처음으로 도달하는 노드는8입니다.3은 이 노드의 왼쪽 자식이고,15는 오른쪽에 있는12아래에 있습니다. 루트20도 공통 조상이지만, 더 위에 있습니다.
- 입력
- tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
- 출력
- 12
- 설명
10은12의 왼쪽 자식이며, 노드는 자기 자신의 조상으로 간주되므로12가 두 값을 모두 포함하고 그 아래의 어떤 노드도 그렇지 않습니다. 여기서p는 더 큰 값입니다.
- 입력
- tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
- 출력
- 70
- 설명
- 두 값 모두 루트
50보다 크므로 둘 다 루트의 오른쪽에 있습니다.70에서 경로가 갈라집니다.55는 더 작아60아래 왼쪽에 있고,80은 더 큽니다.
후속 질문
p 또는 q가 트리에 없을 수도 있고, 그런 경우 함수가 -1을 반환해야 한다면 무엇을 바꾸시겠어요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
루트에 서세요.
p와q가 모두 루트의 값보다 작다면, 두 노드는 어느 하위 트리에 있나요?두 값이 모두 현재 노드의 같은 쪽에 있는 한, 더 아래쪽에 있는 모든 공통 조상도 그쪽에 있습니다. 두 값이 서로 다른 쪽에 있거나 노드가 둘 중 하나를 담고 있는 첫 번째 노드가 찾으려는 노드입니다.
인덱스
0에서 시작합니다. 두 값이 모두tree[i]보다 작으면2*i+1로 이동하고, 두 값이 모두 더 크면2*i+2로 이동합니다. 그렇지 않으면tree[i]를 반환합니다.
풀이
탐색 트리는 각 노드에서 값이 어디에 있는지 알려 줍니다. 더 작은 값은 왼쪽에, 더 큰 값은 오른쪽에 있습니다. 루트에서 시작해 두 값이 모두 있는 쪽으로 이동합니다. 두 값이 더 이상 같은 쪽에 있지 않게 되는 첫 번째 노드가 정답이며, 하나의 경로를 따라 그 노드에 도달합니다.
순서를 무시하고 트리 전체를 검색합니다
핵심 아이디어
이 방법은 모든 이진 트리에서 작동합니다. 재귀적인 find(i)는 i에 있는 하위 트리가 무엇을 포함하는지 알려줍니다. p 또는 q를 포함하는 노드는 자기 자신을 반환합니다. 다른 값이 그 아래에 있으면 그 노드가 답이고, 그렇지 않으면 더 위에 있는 노드가 둘 다 찾습니다. 그 밖의 모든 노드는 양쪽 자식 노드에 묻습니다. 양쪽 모두 무언가를 반환하면 p와 q는 서로 다른 쪽에 있으며 이 노드에서 만납니다. 한쪽만 반환하면 그 값을 위로 전달합니다.
3과 15의 경우, 8은 왼쪽에서 인덱스 3을, 오른쪽에서 인덱스 10을 받고 자기 자신을 반환합니다. 모든 노드를 방문할 수도 있습니다. 시간 복잡도는 O(n)이고, 재귀에 O(h)의 공간이 필요합니다.
알고리즘
find(i)를 작성합니다.i위치가 비어 있으면 (끝을 지났거나-1이면)-1을 반환합니다.tree[i]가p또는q이면i를 반환합니다.2*i+1과2*i+2에 대해find를 호출합니다. 둘 다 무언가를 찾았다면i를 반환합니다.- 그렇지 않으면 무언가를 찾은 쪽을 반환하거나
-1을 반환합니다. tree[find(0)]을 반환합니다.
def lowestCommonAncestor(tree, p, q):
n = len(tree)
def find(i):
# In the subtree at index i: the index of the answer if both values are
# inside, the index of the one that is, or -1 when neither is.
if i >= n or tree[i] == -1:
return -1
if tree[i] == p or tree[i] == q:
return i
left = find(2 * i + 1)
right = find(2 * i + 2)
if left != -1 and right != -1:
return i # one value on each side: this node is the answer
return left if left != -1 else right
return tree[find(0)]두 검색 경로를 비교하세요
핵심 아이디어
일반적인 방법으로 값을 검색합니다. 루트에서 시작해 값이 노드보다 작으면 왼쪽으로, 크면 오른쪽으로 이동합니다. 루트에서 노드까지의 경로는 하나뿐이므로, 탐색 과정에서는 해당 값의 모든 조상을 지나고 다른 노드는 지나지 않습니다.
두 경로를 모두 기록합니다. 값이 서로 다른 방향으로 갈 때까지 두 경로는 노드를 공유하므로, 처음에 겹치는 부분이 공통 조상을 나열하며 그중 마지막 값이 가장 낮은 조상입니다. 3과 15의 경로는 20, 8, 3과 20, 8, 12, 15입니다. 20, 8을 공유하므로 답은 8입니다. 각 탐색은 레벨마다 한 단계씩 이동하므로 시간은 O(h)이고, 목록을 저장하는 데 O(h)의 공간이 필요합니다.
알고리즘
path(target)를 작성하세요. 인덱스0에서 시작해tree[i]를 기록하고, 이것이target과 같으면 멈추세요. 그렇지 않으면target이 더 작을 때2*i+1로, 더 클 때2*i+2로 이동하세요.p까지의 경로와q까지의 경로를 만드세요.- 두 목록을 처음부터 함께 살펴보고, 두 목록에 공통으로 있는 마지막 값을 반환하세요.
def lowestCommonAncestor(tree, p, q):
def path(target):
# The values met on the way from the root down to target.
values = []
i = 0
while True:
values.append(tree[i])
if tree[i] == target:
return values
i = 2 * i + 1 if target < tree[i] else 2 * i + 2
to_p, to_q = path(p), path(q)
# Both paths start at the root; the answer is the last value they share.
answer = to_p[0]
for a, b in zip(to_p, to_q):
if a != b:
break
answer = a
return answer값이 갈라질 때까지 내려갑니다
핵심 아이디어
p와 q가 같은 방향으로 이동하는 동안 두 경로는 일치하므로, 둘을 동시에 따라가세요. v를 담고 있는 노드에서 두 값이 모두 더 작으면 둘 다 왼쪽 하위 트리에 있으며, v 아래에 있는 모든 공통 조상도 마찬가지이므로 왼쪽으로 이동하세요. 두 값이 모두 더 크면 오른쪽으로 이동하세요.
그렇지 않으면 한 값은 더 작고 다른 값은 더 크므로 v의 어느 자식도 두 값을 모두 포함하지 않거나, 둘 중 하나가 v와 같으며 이 경우 v는 자기 자신의 조상입니다. 어느 경우든 v는 두 값 위에 있는 가장 깊은 노드입니다. 세 번째 예시에서 50은 두 값보다 작으므로 오른쪽으로 70까지 이동합니다. 여기서 55는 더 작고 80은 더 큽니다. 각 레벨에서 비교를 한 번씩 하면 시간 복잡도는 O(h), 공간 복잡도는 O(1)입니다.
알고리즘
- 인덱스
i = 0에서 시작합니다. v = tree[i]를 읽습니다.p < v이고q < v이면2*i+1로 이동한 다음 반복합니다.p > v이고q > v이면2*i+2로 이동한 다음 반복합니다.- 그렇지 않으면
v를 반환합니다.
def lowestCommonAncestor(tree, p, q):
i = 0 # start at the root
while True:
value = tree[i]
if p < value and q < value:
i = 2 * i + 1 # both are smaller: the answer is on the left
elif p > value and q > value:
i = 2 * i + 2 # both are larger: the answer is on the right
else:
return value # they split here, or one of them is this node
함정과 경계 사례
- 이동 테스트에서
≤와≥를 사용하는 경우.p = 12이고q = 10이면, 탐색이12를 지나10으로 이동한 다음10을 반환하거나 트리의 범위를 벗어납니다. p < q라고 가정하는 경우. 두 번째 예제에서는p가 더 큰 값입니다. 둘 다 노드와 비교하거나, 먼저 두 값을 서로 바꾸세요.- 값 대신 인덱스를 반환하는 경우. 답은
i가 아니라tree[i]입니다. - Lua와 R에서는 배열이 1부터 시작합니다.
2*i+1산술을 위해 노드 인덱스는 0부터 시작하도록 유지하고tree[i + 1]을 읽으세요.
자주 묻는 질문3
BST에서 최소 공통 조상의 시간 복잡도는 얼마인가요?
루트에서 시작하는 탐색은 하나의 경로를 따라가므로, 깊이가 h인 트리에서 O(h) 시간이 걸리고 추가 공간은 O(1)입니다. 균형 트리에서는 O(log n)이고, 하나의 경로처럼 생긴 트리에서는 O(n)입니다.
이진 검색 트리의 LCA는 이진 트리의 LCA와 어떻게 다른가요?
일반적인 이진 트리에서는 값이 어디에나 있을 수 있으므로 모든 노드를 검색해야 하며, 작업량은 O(n)입니다. 검색 트리에서는 두 값을 노드와 비교하면 각 값이 어느 쪽에 있는지 알 수 있으므로 루트에서 한 경로를 따라가면 됩니다.
노드가 자신의 최저 공통 조상일 수 있나요?
네. 노드는 자기 자신의 조상으로 간주되므로, p가 q보다 위에 있으면 답은 p이고, 두 값이 같으면 그 값이 답입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def lowestCommonAncestor(tree, p, q):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15] p = 3 q = 15
예상 출력
8