Lowest Common Ancestor of a Binary Tree

Q: 이것은 이진 탐색 트리에서의 최저 공통 조상과 어떻게 다른가요?

검색 트리에서는 p 와 q 를 노드와 비교하면 각각 어느 쪽에 있는지 알 수 있으므로, 루트에서 한 경로만 따라가면 O(h)에 답을 찾을 수 있습니다. 여기서는 비교해도 알 수 있는 것이 없으므로 하위 트리들을 검색합니다.

Q: 부모 포인터를 사용해 가장 낮은 공통 조상을 찾을 수 있나요?

네. 이 배열에서 인덱스 i 의 부모는 (i-1)/2 를 내림한 값입니다. 두 인덱스 중 더 큰 인덱스를 부모로 옮겨 둘이 같아질 때까지 반복하세요. 더 큰 인덱스가 더 작은 인덱스의 조상인 경우는 없습니다. 연결된 노드에서는 p 의 조상들을 집합에 넣고, q 에서 위로 올라가며 집합에 처음 포함되는 노드를 찾으세요.

보통트리 순회 재귀

+10

힙 순서로 배열 root에 저장된 이진 트리가 주어집니다. 루트는 인덱스 0에 있고, 인덱스 i의 자식은 2*i+1(왼쪽)과 2*i+2(오른쪽)에 있으며, 비어 있는 위치는 -1로 표시됩니다. 값은 서로 다르며 어떤 순서도 따르지 않습니다.

서로 다른 두 노드의 값인 p와 q의 최소 공통 조상, 즉 두 노드를 모두 포함하는 서브트리 중 가장 깊은 노드의 값을 반환하세요. 서브트리에는 최상위 노드도 포함되므로, q가 p 아래에 있으면 정답은 p입니다.

함수

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

rootinteger-array: 레벨 순서로 표현한 이진 트리이며, 빈 위치는 -1로 표시합니다
pinteger: 노드 하나의 값
qinteger: 다른 노드의 값
반환값integer: 하위 트리에 p와 q를 모두 포함하는 가장 낮은 노드의 값

제약 조건

2 ≤ root.length ≤ 32767
각 root[i]는 -1이거나 0 ≤ root[i] ≤ 10⁴인 값입니다.
root[0]은 절대로 -1이 아니며, 트리에는 노드가 최소 두 개 있습니다.
배열은 마지막 노드 뒤에 추가 -1 항목이 있을 수 있습니다.
빈 자리의 두 자식도 모두 비어 있으며, 깊이는 최대 14입니다.
트리의 모든 값은 서로 다르며, 특정한 순서를 따르지 않습니다.
p와 q는 트리에서 서로 다른 두 노드의 값이며, 순서는 상관없습니다.

예제

입력: root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 6q = 9
출력: 3
설명: 6은 3의 왼쪽 자식이고, 9는 3의 오른쪽에 있는 4 아래에 있으므로 두 값은 3에서 만납니다. 값을 비교하면 루트 8을 가리키게 됩니다. 6은 더 작고 9는 더 큽니다.

입력: root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 4q = 7
출력: 4
설명: 7은 4의 왼쪽 자식이고, 4의 하위 트리에는 4 자체가 포함되므로 정답은 4입니다.

입력: root = [1, -1, 6, -1, -1, 3, 0, -1, -1, -1, -1, -1, -1, -1, -1]p = 3q = 0
출력: 6
설명: 루트 1에는 왼쪽 자식이 없습니다. 오른쪽 자식인 6의 왼쪽에는 3이 있고 오른쪽에는 0이 있으므로, 값은 6에서 만납니다.

후속 질문

p 또는 q가 없을 수도 있고 답이 -1인 경우, 단일 패스에서 어떤 지름길이 작동하지 않으며, 한 번의 순회로 어떻게 여전히 완료할 수 있나요?

힌트

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

3개 중 0개 열림

풀이

어느 쪽에 값이 있는지 알려 주는 순서는 없으므로 직접 살펴봐야 합니다. 후위 순회 한 번이면 각 하위 트리가 찾은 값을 알려 주고, 양쪽 모두에서 소식을 들은 첫 번째 노드에서 값들이 만납니다.

아래로 내려가며 양쪽을 살펴보세요

핵심 아이디어

루트에서 아래로 내려가며 각 노드에서 왼쪽 하위 트리에 p와 q가 있는지 검색합니다. 둘 다 있으면 왼쪽으로 갑니다. 둘 다 없으면 오른쪽으로 갑니다. 하나씩 있으면 두 값이 갈라지는 것이므로 현재 노드가 답입니다. p 또는 q를 가진 노드도 답이 될 수 있습니다. 다른 값은 그 아래에 있어야 하기 때문입니다. 6과 9의 경우 루트는 둘 다 왼쪽에서 찾고, 3에서는 6만 있어 p만 찾습니다.

아래로 내려갈 때마다 하위 트리 전체를 검색하므로, 높이가 h인 경우 비용은 O(n·h)이며, 깊이 제한이 없는 키 크고 폭이 좁은 트리에서는 O(n²)입니다. 8에서 검색할 때 이미 3 아래의 모든 노드를 방문했고, 3에서 진행하는 단계에서 일부 노드를 다시 방문합니다.

알고리즘

contains(i, value)를 작성하세요. 빈 위치(끝을 지났거나 -1)이면 false, root[i]가 value와 같으면 true를 반환하고, 그렇지 않으면 양쪽 자식에 모두 확인합니다.
i = 0에서 시작합니다. root[i]가 p 또는 q이면 이를 반환합니다.
2*i+1의 왼쪽 하위 트리에 두 값이 모두 있으면 그쪽으로 이동합니다. 둘 다 없으면 2*i+2로 이동합니다.
그렇지 않으면 root[i]를 반환합니다.

def lowestCommonAncestor(root, p, q):
    n = len(root)

    def contains(i, value):
        # Is value somewhere in the subtree at index i?
        if i >= n or root[i] == -1:
            return False
        if root[i] == value:
            return True
        return contains(2 * i + 1, value) or contains(2 * i + 2, value)

    i = 0  # p and q are always inside the subtree at i
    while True:
        if root[i] == p or root[i] == q:
            return root[i]  # one value is here, the other is below it
        left = 2 * i + 1
        p_left = contains(left, p)
        q_left = contains(left, q)
        if p_left and q_left:
            i = left  # both on the left
        elif not p_left and not q_left:
            i = 2 * i + 2  # both on the right
        else:
            return root[i]  # one on each side

한 번의 후위 순회

핵심 아이디어

모든 부분 트리가 아래에서 위로 한 번씩 답을 반환하게 하세요. find(i)는 i에 있는 부분 트리에 두 값이 모두 있으면 답의 인덱스를, 하나만 있으면 p 또는 q의 인덱스를, 둘 다 없으면 -1을 반환합니다.

p 또는 q를 가진 노드는 아래를 살펴보지 않고 자신의 인덱스를 반환합니다. 다른 값이 그 노드의 부분 트리에 있으면 이 노드가 답입니다. 그렇지 않으면 더 위에 있는 노드가 양쪽에서 결과를 받습니다. 그 밖의 노드는 두 자식 노드에 모두 물어봅니다. 결과가 두 개라면 값들이 서로 다른 쪽에서 올라와 여기서 만난 것이므로, 이 노드가 답입니다. 결과가 하나라면 값 하나이든 이미 결정된 답이든 그대로 위로 전달합니다.

첫 번째 예시에서 3은 왼쪽에서 인덱스 3을, 오른쪽에서 10을 받고 자신의 인덱스 1을 반환하며, 루트 노드는 이를 위로 전달합니다. 각 노드는 한 번씩 방문합니다. 시간 복잡도는 O(n), 재귀 공간 복잡도는 O(h)입니다.

알고리즘

끝을 지난 인덱스이거나 -1이면 find(i)는 -1을 반환합니다.
값이 p 또는 q인 노드는 아래를 살펴보지 않고 i를 반환합니다.
그 외의 노드는 left = find(2*i+1)와 right = find(2*i+2)를 계산합니다. 둘 다 -1이 아니면 i를 반환하고, 그렇지 않으면 -1이 아닌 값을 반환하거나 -1을 반환합니다.
root[find(0)]를 반환합니다.

def lowestCommonAncestor(root, p, q):
    n = len(root)

    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 root[i] == -1:
            return -1
        if root[i] == p or root[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 root[find(0)]

함정과 경계 사례

값을 노드와 비교하는 것. 트리에는 순서가 없습니다. 첫 번째 예시에서 탐색은 3이 아니라 루트 8에서 멈춥니다.
인덱스 대신 true 또는 false를 전달하는 것. 부모 노드는 완료된 답이 이미 자신 아래에 있는지 알 수 없습니다.
길이를 확인하지 않고 자식을 읽는 것. 인덱스 10의 9에는 마지막 항목을 넘어서는 자식 인덱스 21과 22가 있습니다.
root[find(0)]이 아니라 인덱스인 find(0)을 반환하는 것.
Lua와 R에서는 배열이 1부터 시작합니다. 노드 인덱스는 0부터 유지하고 root[i + 1]을 읽으세요.

자주 묻는 질문3

이진 트리의 최소 공통 조상 알고리즘의 시간 복잡도는 얼마인가요?

후위 순회는 각 노드에 최대 한 번 진입하므로 시간 복잡도는 O(n)입니다. 재귀 스택에는 레벨마다 프레임 하나가 저장되므로 균형 트리에서는 공간 복잡도가 O(log n)이고, 경로 형태의 트리에서는 O(n)입니다.

이것은 이진 탐색 트리에서의 최저 공통 조상과 어떻게 다른가요?

검색 트리에서는 p와 q를 노드와 비교하면 각각 어느 쪽에 있는지 알 수 있으므로, 루트에서 한 경로만 따라가면 O(h)에 답을 찾을 수 있습니다. 여기서는 비교해도 알 수 있는 것이 없으므로 하위 트리들을 검색합니다.

부모 포인터를 사용해 가장 낮은 공통 조상을 찾을 수 있나요?

네. 이 배열에서 인덱스 i의 부모는 (i-1)/2를 내림한 값입니다. 두 인덱스 중 더 큰 인덱스를 부모로 옮겨 둘이 같아질 때까지 반복하세요. 더 큰 인덱스가 더 작은 인덱스의 조상인 경우는 없습니다. 연결된 노드에서는 p의 조상들을 집합에 넣고, q에서 위로 올라가며 집합에 처음 포함되는 노드를 찾으세요.

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

테스트 #1

테스트 #2

테스트 #3

인자들

root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]
p = 6
q = 9

예상 출력