Bottom View of Binary Tree

Q: 이진 트리의 하단 뷰의 시간 복잡도는 얼마인가요?

n 개 노드에 대해 O(n) : 너비 우선 탐색은 해시 맵에 한 번씩 쓰면서 모든 노드를 한 번씩 처리합니다. 트리 맵과 같은 정렬된 맵은 w 개 열에 대해 log w 인자를 추가합니다.

보통트리 순회 해싱

+10

배열 root에는 이진 트리가 들어 있습니다. 루트는 인덱스 0에 있고, 인덱스 i의 자식은 2i+1(왼쪽)과 2i+2(오른쪽)에 있으며, 빈 자리는 -1로 표시하고 끝에 추가로 -1 항목이 있을 수도 있습니다.

루트는 열 0에 있습니다. 왼쪽으로 한 단계 이동하면 열이 하나 왼쪽으로, 오른쪽으로 한 단계 이동하면 열이 하나 오른쪽으로 이동합니다. 아래에서 보았을 때 각 열에는 가장 깊은 노드가 표시되고, 깊이가 같으면 왼쪽에서 오른쪽으로 읽었을 때 해당 레벨에서 마지막 노드(인덱스가 더 큰 노드)가 표시됩니다. 보이는 값들을 가장 왼쪽 열부터 반환하세요.

함수

bottomView(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, 1, 9, 6]
설명: 열 0에는 5가 있고, 두 단계 아래에는 7(인덱스 4)과 1(인덱스 5)이 있습니다. 같은 레벨에서 1이 더 나중에 오므로 표시됩니다. 열 -2, -1, 1, 2에는 4, 2, 9, 6이 있습니다.

입력: root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
출력: [5, 4, 3]
설명: 열 -1에는 2가 있고, 두 단계 아래에는 5(인덱스 9)가 있으므로 5가 보입니다. 열 0에서는 루트 아래에 4가 있습니다. 열 1에는 3만 있습니다.

입력: root = [8, -1, -1, -1]
출력: [8]
설명: 루트 뒤의 모든 위치는 -1이므로, 8이 유일한 노드이고 열 0이 유일한 열입니다.

후속 질문

열의 가장 깊은 수준에서 동률인 경우 동률인 모든 노드를 왼쪽에서 오른쪽 순서로 반환해야 한다면, 너비 우선 버전은 어떻게 달라질까요? 예제 1의 열 0에서는 어떤 결과가 나올까요?

풀이

각 열에는 가장 깊은 노드가 표시되고, 깊이가 같으면 레벨 순서에서 더 나중에 나오는 노드를 선택합니다. 너비 우선 탐색은 노드를 레벨 순서로 방문하므로, 각 열에서 마지막으로 방문하는 노드가 정답입니다. 모든 노드가 해당 열의 슬롯을 덮어쓰도록 하세요.

깊이 우선 탐색, 열별 가장 깊은 노드

핵심 아이디어

트리를 깊이 우선으로 순회하면서 각 노드에 열과 깊이를 전달하고, 각 열마다 지금까지 가장 깊은 노드의 깊이와 값을 저장합니다.

왼쪽 하위 트리를 오른쪽 하위 트리보다 먼저 방문하면 한 레벨의 노드를 왼쪽에서 오른쪽 순서로 만나므로, 원하는 노드는 마지막으로 만나는 노드입니다. 깊이가 더 크거나 같을 때 값을 바꿉니다. 예제 1에서는 순회 중 열 0에서 깊이 2인 7과 1을 차례로 만나고, 1이 해당 열의 값을 차지합니다.

열은 끊김 없는 범위를 이루므로 최솟값과 최댓값을 추적하고 그 사이의 모든 열을 읽습니다. 각 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)이고, h개 레벨의 트리에서 재귀 호출 깊이는 h입니다.

알고리즘

열 0, 깊이 0에서 root를 방문합니다.
인덱스 i가 배열의 끝을 벗어나 있거나 root[i]가 -1이면 건너뜁니다.
해당 열에 아직 노드가 없거나 이 깊이가 저장된 깊이보다 크거나 같으면, 이 깊이와 값을 저장합니다.
2i+1을 열 col-1에서 방문한 다음, 한 단계 더 깊은 곳에서 2i+2를 열 col+1에서 방문합니다.
저장된 값을 열이 가장 작은 순서대로 반환합니다.

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

    def visit(i, col, depth):
        if i >= n or root[i] == -1:
            return
        # Replace on a greater or equal depth: on a tie, the node
        # met last is the one further right, which comes later 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인 노드보다 먼저 내보내며, 각 레벨에서는 왼쪽에서 오른쪽 순서로 내보냅니다. 한 열에 있는 노드 중 가장 깊은 노드가 마지막에 나오고, 깊이가 같으면 더 오른쪽에 있는 노드가 나중에 나옵니다. 따라서 각 노드가 해당 열의 슬롯을 덮어쓰면, 각 슬롯에는 깊이를 비교할 필요 없이 아래에서 보이는 노드가 남습니다.

예제 1에서 7은 열 0에 기록되고, 1이 그 값을 덮어씁니다.

각 노드는 큐에서 한 번 방문하고 맵에 한 번 기록되므로 시간 복잡도는 O(n)입니다. 큐에는 한 레벨 전체가 들어갈 수 있으며, 이는 노드의 약 절반이므로 공간 복잡도는 O(n)입니다.

알고리즘

(인덱스 0, 열 0) 쌍을 큐에 넣습니다.
(i, col) 쌍을 꺼내고, root[i]를 col 아래에 저장하며 이전 값이 있으면 바꿉니다.
배열 안에 있고 -1이 아닌 각 자식에 대해 (2i+1, col-1)을 추가한 다음 (2i+2, col+1)을 추가합니다.
큐가 빌 때까지 가장 작은 열과 가장 큰 열을 추적하며 반복합니다.
가장 작은 열부터 맵의 값들을 반환합니다.

from collections import deque


def bottomView(root):
    n = len(root)
    bottom = {}  # column -> value of the last 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 deeper nodes later, and right after left
        # on one level, so the last node to reach a column is the one seen from below.
        bottom[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 [bottom[col] for col in range(min(bottom), max(bottom) + 1)]

함정과 경계 사례

깊이 우선 버전에서는 깊이가 엄격하게 더 깊을 때만 교체합니다. 예제 1에서는 1 대신 7을 유지합니다.
너비 우선 탐색에서 각 열에 처음 방문한 노드를 유지합니다. 이것이 위쪽 뷰입니다.
왼쪽 자식보다 오른쪽 자식을 먼저 큐에 추가합니다. 그러면 각 레벨의 노드가 오른쪽에서 왼쪽 순으로 나오고, 같은 깊이에서는 잘못된 노드가 선택됩니다.
잎 노드를 답으로 선택합니다. 예제 1에서는 잎 노드 7이 1에 가려지고, 예제 2에서는 노드 4에 자식이 있지만 열 0의 맨 아래에 있습니다.
열을 텍스트로 정렬합니다. 문자열로 정렬하면 "-10"은 "-1"과 "-2" 사이에 놓입니다.

자주 묻는 질문3

이진 트리의 아래쪽 뷰란 무엇인가요?

루트에 열 0을 부여하고, 왼쪽으로 한 단계 이동할 때마다 열 번호를 하나씩 줄이고 오른쪽으로 한 단계 이동할 때마다 하나씩 늘립니다. 아래에서 본 모습은 왼쪽에서 오른쪽 순서로 각 열에서 가장 깊은 노드를 나열합니다. 이 문제에서는 깊이가 같은 경우 레벨 순서로 비교하여 나중에 방문한 노드를 선택합니다.

이진 트리의 하단 뷰의 시간 복잡도는 얼마인가요?

n개 노드에 대해 O(n): 너비 우선 탐색은 해시 맵에 한 번씩 쓰면서 모든 노드를 한 번씩 처리합니다. 트리 맵과 같은 정렬된 맵은 w개 열에 대해 log w 인자를 추가합니다.

위에서 본 모습과 아래에서 본 모습의 차이점은 무엇인가요?

둘 다 각 열에서 노드 하나를 선택합니다. 위에서 보는 뷰는 가장 얕은 노드를 선택하고, 아래에서 보는 뷰는 가장 깊은 노드를 선택합니다. 너비 우선 버전에서 위에서 보는 뷰는 각 열이 처음 받는 값을 유지하고, 아래에서 보는 뷰는 값이 들어올 때마다 덮어씁니다.

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

테스트 #1

테스트 #2

테스트 #3

인자

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

예상 출력

[4, 2, 1, 9, 6]