Left View of Binary Tree

Q: 왼쪽 뷰의 시간 및 공간 복잡도는 얼마인가요?

두 해결 방법 모두 각 노드를 한 번씩 살펴보므로 시간 복잡도는 O(n) 입니다. 너비 우선 탐색의 큐에는 한 레벨 전체가 들어가며, 이는 완전 이진 트리 노드 수의 약 절반입니다. 왼쪽 우선 탐색은 레벨마다 호출 하나를 유지하므로, 레벨이 h 개일 때 O(h) 입니다.

쉬움트리 순회 큐

+10

힙 순서의 배열 root로 이진 트리가 주어집니다. 루트는 인덱스 0에 있고, 인덱스 i의 자식은 2*i+1(왼쪽)과 2*i+2(오른쪽)에 있으며, -1은 비어 있는 위치를 나타냅니다. 배열의 끝에 여분의 -1 항목이 있을 수 있습니다.

트리의 왼쪽에 서 있습니다. 각 레벨에서 노드 하나, 즉 가장 왼쪽 노드가 보이고, 그 레벨의 나머지 노드들은 그 뒤에 가려집니다. 위쪽 레벨부터 아래쪽 레벨 순서로 보이는 값을 반환하세요.

함수

leftView(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 = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
출력: [3, 8, 6, 1]
설명: 8은 리프이므로 세 번째와 네 번째 레벨에는 오른쪽 자식 5 아래의 6(인덱스 6)과 1(인덱스 13)만 있습니다. 그래도 이 값들을 볼 수 있습니다: [3, 8, 6, 1].

입력: root = [10, -1, -1]
출력: [10]
설명: 인덱스 1과 2에는 -1이 들어 있으므로, 10에는 자식이 없고 뷰에는 루트만 있습니다.

입력: root = [1, 2, 3, 4, 5, 6, 7]
출력: [1, 2, 4]
설명: 세 단계로 이루어진 전체 트리입니다. 각 단계에서 가장 왼쪽에 있는 위치의 인덱스는 0, 1, 3이며, 여기에 1, 2, 4가 들어 있습니다.

후속 질문

레벨 d는 인덱스 2^d-1부터 2^(d+1)-2까지 채웁니다. 큐나 재귀 없이 해당 범위를 순회하여 뷰를 만들 수 있나요? 패딩된 배열에서는 비용이 얼마나 들까요?

풀이

왼쪽 자식 노드를 따라가면 왼쪽 하위 트리가 더 짧을 때 실패합니다. 첫 번째 예제에서는 오른쪽 하위 트리를 통해 아래쪽 레벨을 보게 됩니다. 각 레벨의 첫 번째 노드를 원합니다. 너비 우선 탐색은 각 레벨의 노드를 왼쪽에서 오른쪽으로 차례로 보여 주고, 왼쪽을 먼저 방문하는 깊이 우선 탐색은 각 레벨에서 가장 왼쪽에 있는 노드를 먼저 만납니다.

너비 우선 탐색, 각 레벨의 첫 번째 노드

핵심 아이디어

라운드별로 처리하는 큐는 한 번에 하나씩 각 레벨을 제공합니다. 라운드가 시작될 때 큐에는 왼쪽에서 오른쪽 순서로 정확히 하나의 레벨이 들어 있습니다. 라운드 중에 추가되는 모든 자식 노드는 해당 레벨 뒤에 들어가기 때문입니다. 그 수만큼 인덱스를 꺼내고, 각 인덱스의 자식 노드를 왼쪽 자식부터 큐에 넣은 다음 첫 번째 값을 유지합니다.

첫 번째 예시의 라운드는 [3], [8, 5], [6], [1]이며, 각각 3, 8, 6, 1을 유지합니다. 자식 위치 3과 4에 -1이 있으므로 8은 아무것도 추가하지 않습니다.

각 노드는 큐에 한 번 들어갔다가 한 번 나옵니다. 시간 복잡도는 O(n)입니다. 큐에는 한 레벨 전체가 들어가며, 14개 레벨의 완전한 트리에서는 인덱스가 최대 8192개 들어갑니다.

알고리즘

인덱스 0을 담은 큐와 빈 답을 준비합니다.
큐가 비어 있지 않은 동안 큐의 크기를 s라고 하고 인덱스 s개를 꺼냅니다. 첫 번째 인덱스의 값을 답에 추가합니다.
꺼낸 각 인덱스 i에 대해 2i+1을 큐에 넣은 다음 2i+2를 큐에 넣습니다. 끝을 넘어가는 인덱스와 -1인 항목은 건너뜁니다.

from collections import deque


def leftView(root):
    n = len(root)
    view = []
    queue = deque([0])  # node indexes; the root is never empty
    while queue:
        size = len(queue)  # exactly the nodes of the current level
        for j in range(size):
            i = queue.popleft()
            if j == 0:
                view.append(root[i])  # the first node of this level
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and root[child] != -1:
                    queue.append(child)
    return view

깊이 우선, 왼쪽 자식 우선

핵심 아이디어

깊이 우선으로 순회하며 왼쪽 하위 트리를 오른쪽 하위 트리보다 먼저 방문하고, 각 노드의 깊이를 전달합니다. 순회가 깊이 d에 도달했을 때 처음 만나는 노드가 레벨 d에서 가장 왼쪽에 있는 노드입니다. 어떤 레벨에서 가장 왼쪽에 있는 노드 x와 그 오른쪽에 있는 임의의 노드 y를 살펴보면, 두 경로가 마지막으로 공유하는 노드에서 x는 왼쪽으로 가고 y는 오른쪽으로 갑니다. 순회는 왼쪽 가지를 모두 마친 뒤 오른쪽으로 넘어갑니다.

순회는 한 번에 한 레벨씩 내려가므로, 깊이 d에 처음 도달했을 때 답에는 정확히 d개의 값이 들어 있습니다. d가 답의 길이와 같을 때 노드를 기록하면 됩니다. 이미 방문한 깊이를 저장하는 집합은 필요하지 않습니다.

각 노드는 한 번 방문하며, 시간 복잡도는 O(n)이고 메모리에는 레벨마다 호출 하나가 저장되므로 여기서는 최대 14개입니다. R 버전은 자체 스택을 유지하며 오른쪽 자식을 왼쪽 자식보다 먼저 넣습니다.

알고리즘

빈 answer를 만들고 visit(0, 0)을 호출합니다.
visit(i, d)에서 i가 배열의 범위를 벗어나거나 root[i]가 -1이면 즉시 반환합니다.
d가 answer의 길이와 같으면, 순회가 처음으로 레벨 d에 도달한 것입니다. root[i]를 추가합니다.
visit(2i+1, d+1)을 호출한 다음 visit(2i+2, d+1)을 호출합니다.
첫 번째 호출이 끝나면 answer를 반환합니다.

def leftView(root):
    n = len(root)
    view = []

    def visit(i, depth):
        if i >= n or root[i] == -1:
            return
        if depth == len(view):  # the first node met on this level
            view.append(root[i])
        # Left before right, so the leftmost node of every level comes first.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return view

함정과 경계 사례

루트에서 왼쪽 자식만 따라갑니다. 첫 번째 예시에서는 8에서 멈추고 6과 1을 놓칩니다.
각 레벨의 첫 번째 슬롯인 root[2^d-1]을 읽습니다. 첫 번째 예시에서는 세 번째 레벨의 첫 슬롯인 인덱스 3에 -1이 있지만, 해당 레벨의 유일한 노드는 인덱스 6에 있습니다.
깊이 우선 탐색에서 오른쪽 자식을 먼저 방문합니다. 그러면 각 레벨에서 처음 만나는 노드는 가장 오른쪽에 있는 노드입니다.
범위를 확인하지 않고 자식을 읽습니다. 인덱스 13의 1에는 자식 위치 27과 28이 있지만, 14개 항목 배열의 끝을 넘어섭니다.

자주 묻는 질문3

왼쪽 뷰는 트리의 왼쪽 경계와 같은가요?

아니요. 왼쪽 경계는 경로입니다. 루트의 왼쪽 자식에서 시작해 왼쪽으로 갈 수 있으면 왼쪽으로, 그렇지 않으면 오른쪽으로 이동하고, 리프에 도달하기 전에 멈춥니다. 왼쪽 뷰는 어느 분기에서든 각 레벨의 노드 하나를 선택합니다. 첫 번째 예시에서는 8이 리프이므로 경계가 비어 있지만, 뷰에는 8, 6, 1이 표시됩니다.

왼쪽 뷰의 시간 및 공간 복잡도는 얼마인가요?

두 해결 방법 모두 각 노드를 한 번씩 살펴보므로 시간 복잡도는 O(n)입니다. 너비 우선 탐색의 큐에는 한 레벨 전체가 들어가며, 이는 완전 이진 트리 노드 수의 약 절반입니다. 왼쪽 우선 탐색은 레벨마다 호출 하나를 유지하므로, 레벨이 h개일 때 O(h)입니다.

올바른 뷰를 얻으려면 솔루션을 어떻게 변경해야 하나요?

너비 우선 버전에서는 각 라운드의 첫 번째 값 대신 마지막 값을 유지하세요. 깊이 우선 버전에서는 왼쪽 자식보다 오른쪽 자식을 먼저 방문하세요. 그러면 각 레벨에서 탐색이 처음 도달하는 노드는 가장 오른쪽에 있는 노드가 됩니다.

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

테스트 #1

테스트 #2

테스트 #3

인자

root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]

예상 출력

[3, 8, 6, 1]