Lowest Common Ancestor of a BST

Q: BST에서 가장 낮은 공통 조상의 시간 복잡도는 얼마인가요?

루트에서의 탐색은 하나의 경로를 따라가므로 깊이가 h 인 트리에서 O(h) 시간이 걸리고 추가 공간은 O(1) 입니다. 균형 트리에서는 O(log n) 이고, 단일 경로처럼 생긴 트리에서는 O(n) 입니다.

Q: 이진 탐색 트리의 LCA는 이진 트리의 LCA와 어떻게 다른가요?

일반적인 이진 트리에서는 값이 어디에든 있을 수 있으므로 모든 노드의 두 하위 트리를 모두 검색해야 하며, 작업량은 O(n) 입니다. 이진 탐색 트리에서는 두 값과 노드의 값을 비교하면 각 값이 어느 쪽에 있는지 알 수 있으므로 루트에서 한 경로만 따라가면 됩니다. 재귀적인 일반 트리 방식도 이진 탐색 트리에서 여전히 작동하지만, 그 정보를 버립니다.

Q: 노드가 자기 자신의 최소 공통 조상이 될 수 있나요?

네. 노드는 자기 자신의 조상으로 간주되므로, p 가 q 위에 있으면 답은 p 입니다. 두 값이 같은 경우에도 같은 규칙에 따라 p 가 답입니다. 이 탐색은 두 경우를 모두 처리합니다. 현재 노드가 두 값 중 하나와 같아지는 즉시 멈춥니다.

Q: p와 q가 갈라지는 첫 번째 노드에서 탐색이 멈추는 이유는 무엇인가요?

그 노드에서 한 값은 더 작고 다른 값은 더 크므로, 두 값은 서로 다른 하위 트리에 있습니다. 그 아래의 어떤 노드도 둘 중 하나의 하위 트리에만 속하므로 두 값을 모두 가질 수 없습니다. 두 갈래로 나뉘는 노드에는 두 값이 모두 있고 그보다 더 아래에는 두 값을 모두 가진 노드가 없으므로, 이것이 바로 가장 낮은 공통 조상의 정의입니다.

보통이진 탐색 트리

+10

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

lowestCommonAncestor라는 함수를 작성하여 p와 q의 가장 낮은 공통 조상의 값, 즉 두 노드가 모두 하위 트리에 포함되는 가장 깊은 노드의 값을 반환하세요. 노드 자체도 자신의 하위 트리에 포함되므로, p가 q보다 위에 있으면 답은 p 자체입니다.

함수

lowestCommonAncestor(tree: integer-array, p: integer, q: integer) → integer

treeinteger-array: 이진 검색 트리를 레벨 순서로 나열하며, 빈 위치는 -1로 표시합니다
pinteger: 찾을 첫 번째 값
qinteger: 찾을 두 번째 값
반환값integer: p와 q를 모두 하위 트리에 포함하는 가장 깊은 노드의 값

제약 조건

1 ≤ tree.length ≤ 32767
각 tree[i]는 -1이거나 0 ≤ tree[i] ≤ 10⁵인 값입니다.
tree[0]은 절대 -1이 아니므로 트리에는 노드가 하나 이상 있습니다.
배열은 마지막 노드 이후에 -1 항목이 추가로 올 수 있습니다.
비어 있는 위치의 두 자식도 비어 있으며, 깊이는 최대 14입니다.
이 트리는 유효한 이진 탐색 트리이므로 모든 값이 서로 다릅니다.
p와 q는 트리에서 노드의 값입니다. 순서는 정해져 있지 않으며 서로 같을 수도 있습니다.

예제

입력: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
출력: 8
설명: 3은 8의 왼쪽 자식이고, 15는 8의 오른쪽에 있는 12 아래에 있습니다. 각각의 노드에서 위로 올라갈 때 둘 다 처음으로 도달하는 노드는 8이므로, 답은 8입니다. 루트인 20도 공통 조상이지만 더 위에 있습니다.

입력: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
출력: 12
설명: 10은 12의 왼쪽 자식입니다. 노드는 자기 자신의 조상으로 간주되므로 12의 하위 트리에는 두 값이 모두 있지만 그 아래의 어떤 노드에도 두 값이 모두 없습니다. 따라서 답은 12입니다. 값은 어느 순서로든 주어질 수 있으며, 여기서는 p가 더 큰 값입니다.

입력: tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
출력: 70
설명: 55와 80은 모두 루트 50보다 크므로 둘 다 오른쪽에 있습니다. 70에서 경로가 갈라집니다. 55는 더 작아서 왼쪽(60 아래)에 있고, 80은 더 커서 오른쪽에 있습니다. 따라서 답은 70입니다.

제출 시 숨은 테스트 +12개

후속 질문

p 또는 q가 트리에 없을 수도 있고, 그런 경우 함수가 -1을 반환해야 한다면 무엇을 변경하시겠어요?

힌트

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

3개 중 0개 열림

풀이

일반적인 이진 트리에서는 모든 노드의 양쪽을 모두 검색하지 않고는 값이 어디에 있는지 알 수 없습니다. 검색 트리는 각 노드에서 더 작은 값은 왼쪽에, 더 큰 값은 오른쪽에 있다고 알려줍니다. 따라서 루트에서 시작해 두 값이 있는 쪽으로 이동하세요. 두 값이 더 이상 같은 쪽에 있지 않게 되는 첫 번째 노드가 정답이며, 트리의 나머지 부분은 전혀 살펴보지 않고 한 경로만 따라가면 찾을 수 있습니다.

순서를 무시하고 전체 트리 검색

핵심 아이디어

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

첫 번째 방법은 어떤 이진 트리에도 적용됩니다. 재귀 함수 find(i)는 i에 있는 하위 트리에 무엇이 있는지 알려줍니다. 빈자리는 -1을 반환합니다. p 또는 q를 가진 노드는 자기 자신을 반환합니다. 다른 값이 그 아래에 있으면 이 노드가 답이고, 다른 값이 다른 곳에 있으면 더 위에 있는 노드가 둘 다를 찾게 됩니다. 그 외의 경우 노드는 양쪽 자식에게 모두 물어봅니다. 양쪽에서 모두 무언가를 반환하면 p는 한쪽에, q는 다른 쪽에 있으므로 이 노드에서 둘이 만납니다. 한쪽에서만 무언가를 반환하면 그것을 위로 전달합니다.

p = 3이고 q = 15인 경우, 8은 왼쪽에서 인덱스 3을, 오른쪽에서 인덱스 10을 받아 자기 자신을 반환합니다. 루트는 왼쪽에서 이 값을 받고 오른쪽에서는 -1을 받아 8을 위로 전달합니다.

이 방법은 올바르지만 모든 노드를 방문할 수도 있으므로 시간 복잡도는 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)]

두 검색 경로 비교

핵심 아이디어

이제 순서를 활용하세요. 탐색 트리에서 값을 찾는 방식대로 값을 찾을 수 있습니다. 루트에서 시작해 값이 노드보다 작으면 왼쪽으로, 크면 오른쪽으로 이동하고, 값을 찾으면 멈춥니다. 루트에서 노드까지의 경로는 유일하므로, 이 경로에는 해당 값의 모든 조상이 지나가며 다른 노드는 지나가지 않습니다.

p를 찾는 경로와 q를 찾는 경로를 기록하세요. 두 경로는 루트에서 시작해 값이 서로 다른 방향으로 갈 때까지 같은 노드들을 따라갑니다. 처음에 공통으로 지나는 부분이 두 값의 공통 조상 목록이므로, 그중 마지막 값이 가장 낮은 조상입니다. 3과 15의 경로는 20, 8, 3과 20, 8, 12, 15입니다. 두 경로는 20, 8을 공유하므로 정답은 8입니다. 12와 10의 경로는 20, 8, 12와 20, 8, 12, 10이며, 정답은 12입니다.

각 경로 탐색은 레벨마다 한 단계씩 진행되므로 시간 복잡도는 O(h)입니다. 여기서는 트리에 노드가 몇 개 있든 최대 14단계입니다. 두 목록은 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와 같을 수 있는데, 노드는 자기 자신의 조상입니다. 어느 경우든 v는 두 값 모두의 위에 있는 가장 깊은 노드입니다.

세 번째 예시에서 루트 50은 55와 80보다 아래에 있으므로, 오른쪽으로 이동해 70에 도달합니다. 여기서 55는 더 작고 80은 더 크므로 답은 70입니다. 두 번째 예시에서는 20에서 8을 거쳐 12로 이동하며, 이는 p와 같으므로 멈춥니다.

루트에서 시작해 레벨마다 비교 한 쌍씩, 단일 경로를 따라가므로 시간 복잡도는 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일 때, p ≤ 12이고 q ≤ 12라는 조건을 검사하면 답인 10을 지나쳐 버리고, 그 지점에서 탐색은 10을 반환하거나 트리의 범위를 벗어납니다. 두 값이 모두 한쪽에 엄격하게 놓여 있을 때만 이동하세요.
p < q라고 가정하는 경우입니다. 값은 어떤 순서로든 주어질 수 있습니다. 두 값을 모두 노드와 비교하거나, 먼저 순서를 바꿔 p가 더 작은 값이 되도록 하세요.
한 값이 다른 값의 조상일 수 있다는 점을 잊는 경우입니다. 이때 답은 그 값 자체이지, 그 부모가 아닙니다.
값 대신 인덱스를 반환하는 경우입니다. 함수는 i가 아니라 tree[i]를 반환합니다.
트리 전체를 탐색하는 경우입니다. 정답은 맞게 찾지만, 한 경로만으로 충분한데도 모든 노드까지 방문할 수 있습니다.
배열의 인덱스가 1부터 시작하는 Lua와 R에서 오프셋을 혼동하는 경우입니다. 2*i+1 계산에는 노드 인덱스를 0부터 시작하도록 유지하고, tree[i + 1]을 읽으세요.

자주 묻는 질문4

BST에서 가장 낮은 공통 조상의 시간 복잡도는 얼마인가요?

루트에서의 탐색은 하나의 경로를 따라가므로 깊이가 h인 트리에서 O(h) 시간이 걸리고 추가 공간은 O(1)입니다. 균형 트리에서는 O(log n)이고, 단일 경로처럼 생긴 트리에서는 O(n)입니다.

이진 탐색 트리의 LCA는 이진 트리의 LCA와 어떻게 다른가요?

일반적인 이진 트리에서는 값이 어디에든 있을 수 있으므로 모든 노드의 두 하위 트리를 모두 검색해야 하며, 작업량은 O(n)입니다. 이진 탐색 트리에서는 두 값과 노드의 값을 비교하면 각 값이 어느 쪽에 있는지 알 수 있으므로 루트에서 한 경로만 따라가면 됩니다. 재귀적인 일반 트리 방식도 이진 탐색 트리에서 여전히 작동하지만, 그 정보를 버립니다.

노드가 자기 자신의 최소 공통 조상이 될 수 있나요?

네. 노드는 자기 자신의 조상으로 간주되므로, p가 q 위에 있으면 답은 p입니다. 두 값이 같은 경우에도 같은 규칙에 따라 p가 답입니다. 이 탐색은 두 경우를 모두 처리합니다. 현재 노드가 두 값 중 하나와 같아지는 즉시 멈춥니다.

p와 q가 갈라지는 첫 번째 노드에서 탐색이 멈추는 이유는 무엇인가요?

그 노드에서 한 값은 더 작고 다른 값은 더 크므로, 두 값은 서로 다른 하위 트리에 있습니다. 그 아래의 어떤 노드도 둘 중 하나의 하위 트리에만 속하므로 두 값을 모두 가질 수 없습니다. 두 갈래로 나뉘는 노드에는 두 값이 모두 있고 그보다 더 아래에는 두 값을 모두 가진 노드가 없으므로, 이것이 바로 가장 낮은 공통 조상의 정의입니다.

Python

def lowestCommonAncestor(tree, p, q):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]
p = 3
q = 15

기대값

Lowest Common Ancestor of a BST

함수

제약 조건

예제

힌트

풀이

순서를 무시하고 전체 트리 검색

두 검색 경로 비교

값이 갈라질 때까지 내려가세요

함정과 경계 사례

자주 묻는 질문4

비슷한 문제