Top View of Binary Tree

Q: 이진 트리의 위에서 본 모습의 시간 복잡도는 얼마인가요?

너비 우선 탐색은 각 n 개 노드를 한 번씩 방문하고 노드당 O(1) 맵 조회를 수행하므로, 가장 작은 열과 가장 큰 열을 추적하면 O(n) 시간이 걸립니다. 열을 정렬된 맵으로 관리하면 열이 w 개일 때 O(n log w) 시간이 걸립니다.

보통트리 순회 해싱

+10

힙 순서로 배열 root에 저장된 이진 트리가 주어집니다. 루트는 인덱스 0에 있고, 인덱스 i의 자식은 2*i+1(왼쪽)과 2*i+2(오른쪽)에 있으며, 빈 자리에는 -1이 있습니다.

루트는 열 0에 있습니다. 왼쪽 자식은 부모보다 한 열 왼쪽에, 오른쪽 자식은 한 열 오른쪽에 위치합니다. 위에서 보면 각 열에서 가장 얕은 노드가 보입니다. 깊이가 같으면 해당 레벨에서 왼쪽부터 먼저 나오는 노드(인덱스가 더 작은 노드)가 보입니다. 가장 왼쪽 열부터 가장 오른쪽 열까지 보이는 값을 반환하세요.

함수

topView(root: integer-array) → integer-array

rootinteger-array: 힙 순서의 트리이며, 빈 위치는 -1로 표시합니다
반환값integer-array: 각 열에서 위에서 본 값, 가장 왼쪽 열부터

제약 조건

1 ≤ root.length ≤ 32767
각 root[i]는 -1이거나 0 ≤ root[i] ≤ 10⁴인 값이며, 같은 값은 두 번 나타나지 않습니다.
root[0]은 절대로 -1이 아니므로 트리에는 노드가 하나 이상 있습니다.
배열은 마지막 노드 뒤에 -1 항목이 더 포함된 채로 끝날 수 있습니다.
빈 자리의 두 자식도 모두 비어 있으며, 트리의 레벨은 최대 14입니다.

예제

입력: root = [5, 2, 9, 4, 7, 1, 6]
출력: [4, 2, 5, 9, 6]
설명: 열은 왼쪽에서 오른쪽으로 4(열 -2), 2(-1), 루트 5(0), 9(1), 6(2)를 담고 있습니다. 7과 1도 열 0에 있지만, 루트는 그 위에 있습니다.

입력: root = [1, 2, -1, -1, 3, -1, -1, -1, -1, -1, 4]
출력: [2, 1, 4]
설명: 2는 열 -1에 있습니다. 인덱스 4에 있는 오른쪽 자식 3은 다시 열 0의 루트 아래에 있으므로 숨겨집니다. 인덱스 10에 있는 3의 오른쪽 자식 4는 열 1에 홀로 있습니다.

입력: root = [6, -1, -1]
출력: [6]
설명: 인덱스 1과 2에는 -1이 들어 있으므로, 6은 열 0에 단독으로 있으며 전체 뷰를 이룹니다.

후속 질문

배열 대신 노드 객체를 사용하면 동률을 결정할 인덱스가 없습니다. 동률 규칙을 어떻게 명시하겠으며, 너비 우선 코드는 달라지나요?

풀이

각 열에는 가장 얕은 노드가 표시되며, 깊이가 같으면 레벨 순서에서 먼저 나오는 노드가 표시됩니다. 이는 너비 우선 탐색이 노드를 방문하는 순서와 정확히 같으므로, 탐색이 해당 열에서 처음 만나는 노드가 정답입니다. 깊이 우선 탐색으로도 가능하지만, 깊이를 추적하고 동률을 주의해서 처리해야 합니다.

깊이 우선 탐색, 열마다 가장 얕은 노드

핵심 아이디어

각 노드의 열과 깊이를 함께 추적하며 트리를 깊이 우선으로 순회하고, 각 열마다 지금까지 찾은 가장 얕은 노드의 깊이와 값을 저장합니다.

깊이가 엄격히 더 작은 경우에만 교체합니다. 깊이가 같은 두 노드 중 레벨 순회에서 먼저 나오는 노드는, 각 왼쪽 하위 트리를 해당 오른쪽 하위 트리보다 먼저 탐색하는 순회에서 먼저 방문됩니다. 두 경로가 갈라지는 지점에서 왼쪽으로 가기 때문입니다. 깊이가 같아도 교체하면 나중 노드가 선택됩니다. 인덱스 3이 비어 있고 인덱스 19와 23에 노드가 있으면, 두 노드 모두 깊이 4의 열 -2에 있으며 정답은 인덱스 19의 노드입니다.

노드가 있는 열은 끊기지 않는 하나의 범위를 이룹니다. 열 -3의 노드에는 열 -1과 -2에 조상이 있기 때문입니다. 따라서 가장 작은 열과 가장 큰 열을 추적합니다. 각 노드는 한 번씩 방문하므로 시간 복잡도는 O(n)이며, 재귀 호출 깊이는 대략 h입니다.

알고리즘

열 0, 깊이 0으로 루트 노드를 방문합니다. 배열 범위를 벗어나거나 -1을 가진 인덱스라면 즉시 반환합니다.
해당 열에 아직 노드가 없거나 이 깊이가 저장된 깊이보다 엄격히 작으면, 이 깊이와 값을 저장합니다.
한 단계 더 깊이 들어가 2i+1을 열 col-1로 방문한 다음, 2i+2를 열 col+1로 방문합니다.
가장 작은 열부터 가장 큰 열까지 저장된 값을 반환합니다.

def topView(root):
    n = len(root)
    best = {}  # column -> (depth, value) of the shallowest node found so far

    def visit(i, col, depth):
        if i >= n or root[i] == -1:
            return
        # Replace only on a strictly smaller depth: on a tie, the node
        # met first is the one further left, which comes first in level order.
        if col not in best or depth < best[col][0]:
            best[col] = (depth, root[i])
        visit(2 * i + 1, col - 1, depth + 1)
        visit(2 * i + 2, col + 1, depth + 1)

    visit(0, 0, 0)
    # The columns that hold a node form one unbroken range.
    return [best[col][1] for col in range(min(best), max(best) + 1)]

너비 우선 탐색, 열마다 첫 번째 노드

핵심 아이디어

루트를 넣은 다음 각 노드의 왼쪽 자식, 오른쪽 자식 순으로 넣는 큐는 노드를 레벨 순서대로 꺼냅니다. 즉 깊이가 d인 모든 노드를 꺼낸 뒤 깊이가 d+1인 노드를 꺼내며, 각 레벨에서는 왼쪽에서 오른쪽 순으로 꺼냅니다. 이것이 문제에서 요구하는 우선순위이므로, 각 열이 받는 첫 번째 노드는 위에서 본 노드이고, 그 뒤에 오는 노드는 모두 건너뜁니다.

각 노드마다 맵 조회가 한 번씩 필요하므로 전체 시간 복잡도는 O(n)입니다. 큐에는 한 레벨 전체가 들어갈 수 있으며, 노드의 약 절반까지 담을 수 있으므로 공간 복잡도는 O(n)입니다.

알고리즘

쌍 (인덱스 0, 열 0)을 큐에 넣습니다.
쌍 (i, col)을 꺼냅니다. 맵에 col에 해당하는 항목이 없으면, 그 위치에 root[i]를 저장합니다.
존재하는 각 자식에 대해 (2i+1, col-1)을 추가한 다음, (2i+2, col+1)을 추가합니다.
큐가 비면, 가장 작은 열부터 가장 큰 열 순서로 맵의 값을 반환합니다.

from collections import deque


def topView(root):
    n = len(root)
    top = {}  # column -> value of the first node seen in that column
    queue = deque([(0, 0)])  # (node index, column); the root is never empty
    while queue:
        i, col = queue.popleft()
        # The queue hands out shallower nodes first, and left before right
        # on one level, so the first node of a column is the one seen from above.
        if col not in top:
            top[col] = root[i]
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and root[left] != -1:
            queue.append((left, col - 1))
        if right < n and root[right] != -1:
            queue.append((right, col + 1))
    # The columns that hold a node form one unbroken range.
    return [top[col] for col in range(min(top), max(top) + 1)]

함정과 경계 사례

깊이 우선 탐색에서 처음 발견한 노드를 유지하는 것. 루트의 왼쪽 자식에게 오른쪽 자식이 있고 그 자식에게도 오른쪽 자식이 있다면(열 1, 깊이 3), 탐색은 루트의 오른쪽 자식(열 1, 깊이 1)보다 그 노드를 먼저 만납니다.
오른쪽 자식을 먼저 큐에 넣는 것: 동률일 때 잘못된 노드가 선택됩니다.
열을 텍스트로 정렬하는 것: "-1"은 "-2"보다 먼저 정렬됩니다.
왼쪽 하위 트리가 음수 열을 채운다고 가정하는 것. 예제 2에서 노드 4는 루트의 왼쪽 하위 트리에 있고 열 1에 있습니다.

자주 묻는 질문3

이진 트리의 위에서 본 모습은 무엇인가요?

루트에서 시작해 열 번호를 0으로 매기고, 왼쪽 자식은 하나씩 왼쪽으로, 오른쪽 자식은 하나씩 오른쪽으로 이동합니다. 위에서 본 뷰에는 왼쪽에서 오른쪽 순서로 각 열에서 루트에 가장 가까운 노드가 나열됩니다.

이진 트리의 위에서 본 모습의 시간 복잡도는 얼마인가요?

너비 우선 탐색은 각 n개 노드를 한 번씩 방문하고 노드당 O(1) 맵 조회를 수행하므로, 가장 작은 열과 가장 큰 열을 추적하면 O(n) 시간이 걸립니다. 열을 정렬된 맵으로 관리하면 열이 w개일 때 O(n log w) 시간이 걸립니다.

윗면도는 왼쪽면도와 아랫면도와 어떻게 다른가요?

왼쪽 뷰는 각 레벨의 첫 번째 노드를 선택합니다. 위쪽 뷰는 각 열에서 가장 얕은 노드를 선택합니다. 아래쪽 뷰는 열마다 가장 깊은 노드를 선택하므로, 이를 위한 너비 우선 탐색은 각 열에서 첫 번째 노드를 유지하는 대신 덮어씁니다.

def topView(root):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

root = [5, 2, 9, 4, 7, 1, 6]

예상 출력

[4, 2, 5, 9, 6]