Binary Tree Right Side View

Q: 이진 트리의 오른쪽 뷰의 시간 복잡도와 공간 복잡도는 무엇인가요?

노드가 n 개일 때 시간 복잡도는 O(n) 이며, 어떤 해법도 노드를 건너뛸 수 없습니다. 한 레벨의 가장 오른쪽 노드는 어디에나 있을 수 있기 때문입니다. 큐의 공간 복잡도는 너비가 가장 넓은 레벨의 너비인 w 에 대해 O(w) 이고, 레벨이 h 개인 트리에서 오른쪽 우선 순회에 필요한 공간 복잡도는 O(h) 입니다.

보통트리 순회 큐

+10

배열 root에는 이진 트리가 들어 있습니다. 루트는 인덱스 0에 있고, 인덱스 i에 있는 노드의 자식은 2*i+1(왼쪽)과 2*i+2(오른쪽)에 있으며, -1은 빈 자리를 나타내고, 끝에 여분의 -1 항목이 올 수 있습니다.

트리를 오른쪽에서 바라보세요. 각 레벨에서는 정확히 하나의 노드, 즉 가장 오른쪽에 있는 노드만 보이고 나머지는 가려집니다. 루트가 있는 레벨부터 가장 깊은 레벨까지 해당 값들을 나열하세요.

함수

rightSideView(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, 7, 4, -1, 1, -1, 3]
출력: [5, 9, 1, 3]
설명: 오른쪽에서 5, 9, 1(인덱스 6)이 보입니다. 네 번째 레벨에는 왼쪽 서브트리에서 7 아래 인덱스 8에 있는 3만 있습니다. 오른쪽에는 그 깊이까지 도달하는 것이 없으므로 3이 보입니다.

입력: root = [6, 0, -1, 8, -1, -1, -1]
출력: [6, 0, 8]
설명: 트리는 왼쪽 자식으로 이어진 사슬입니다: 6, 0, 8. 각 레벨에는 노드가 하나씩 있으므로 세 노드가 모두 표시되지만, 그중 어느 것도 오른쪽 자식은 아닙니다.

입력: root = [42]
출력: [42]
설명: 길이가 1인 배열: 루트 42에는 자식 자리가 전혀 없으며, 뷰는 그 하나의 값입니다.

후속 질문

모든 노드가 임의 개수의 자식을 가질 수 있고, 자식들이 왼쪽에서 오른쪽 순서로 리스트에 저장된 트리의 오른쪽에서 본 모습은 어떻게 구할 수 있을까요?

힌트

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

3개 중 0개 열림

풀이

각 레벨에서 가장 오른쪽에 있는 노드를 보며, 그 노드가 반드시 오른쪽 자식일 필요는 없습니다. 예제 1의 마지막 값은 왼쪽 서브트리에 있습니다. 너비 우선 탐색을 하면 각 라운드에서 그 노드가 마지막에 나오고, 오른쪽을 먼저 방문하는 깊이 우선 탐색을 하면 해당 레벨의 다른 노드보다 먼저 그 노드를 만나게 됩니다.

너비 우선 탐색, 각 레벨의 마지막 노드

핵심 아이디어

트리를 한 라운드마다 한 레벨씩 처리합니다. 라운드가 시작되면 큐에는 왼쪽에서 오른쪽 순서로 정확히 한 레벨의 노드가 들어 있으므로, 해당 라운드에서 마지막으로 큐에서 꺼내는 인덱스는 그 레벨의 가장 오른쪽 노드이며, 그 노드의 값이 정답에 들어갑니다.

예제 1의 라운드는 [5], [2, 9], [7, 4, 1], [3]이며, 각 라운드의 마지막 항목은 5, 9, 1, 3입니다. 기준은 어느 쪽에 있는지가 아니라 레벨입니다. 3은 왼쪽 서브트리에 있지만, 해당 레벨에는 혼자 있습니다.

각 인덱스는 한 번씩 큐에 들어가고 한 번씩 큐에서 나오므로 시간 복잡도는 O(n)입니다. 큐는 가장 너비가 넓은 레벨의 크기까지 커지며, 최악의 경우 O(n)입니다.

알고리즘

루트의 인덱스 0을 큐에 넣습니다.
큐의 길이 s를 저장하여 한 라운드를 시작합니다.
s개의 인덱스를 큐에서 꺼냅니다. 각 인덱스 i에 대해 2i+1이 배열의 길이보다 작고 -1이 아니면 큐에 넣고, 그다음 2i+2도 배열의 길이보다 작고 -1이 아니면 큐에 넣습니다.
해당 라운드에서 마지막으로 큐에서 꺼낸 인덱스의 값을 추가합니다.
큐가 빌 때까지 반복한 다음 답을 반환합니다.

from collections import deque


def rightSideView(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 == size - 1:
                view.append(root[i])  # the last 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

깊이 우선, 오른쪽 자식 노드 우선

핵심 아이디어

깊이 우선으로 순회하면서 왼쪽 자식보다 오른쪽 자식을 먼저 시도하고, 루트의 깊이를 0으로 하여 깊이를 함께 전달합니다. 순회가 깊이 d에 처음 도달했을 때, 답에는 정확히 d개의 값이 들어 있습니다. 그때 노드의 값을 추가하고, 이후 그 깊이에 있는 노드는 모두 무시합니다.

그 첫 번째 노드가 가장 오른쪽에 있는 노드입니다. 어떤 깊이로 향하는 두 경로가 갈라지는 지점이 있으면, 순회는 왼쪽으로 돌아가기 전에 오른쪽 가지를 따라 아래까지 내려갑니다. 예제 1에서 순회는 5, 9, 1, 2, 4, 7, 3을 방문합니다. 깊이에 이미 값이 있는 2, 4, 7은 건너뛰고 3을 추가합니다.

각 노드는 한 번 방문하므로 시간 복잡도는 O(n)이고, 스택에는 깊이마다 호출 하나씩, 최대 14개가 놓입니다.

알고리즘

빈 answer와 깊이 0의 루트로 시작합니다.
배열의 끝을 지난 인덱스이거나 -1을 포함하는 인덱스는 건너뜁니다.
answer의 길이가 깊이와 같으면 값을 추가합니다. 탐색이 새로운 레벨에 도달했으며, 오른쪽에서 그 레벨에 도달했습니다.
먼저 오른쪽 자식 2i+2로 재귀한 다음, 왼쪽 자식 2i+1로 재귀합니다. 각각 한 레벨 더 깊이 들어갑니다.
answer를 반환합니다.

def rightSideView(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])
        # Right before left, so the rightmost node of every level comes first.
        visit(2 * i + 2, depth + 1)
        visit(2 * i + 1, depth + 1)

    visit(0, 0)
    return view

함정과 경계 사례

루트에서 오른쪽 자식만 따라갑니다. 예제 1에서는 [5, 9, 1]을 얻고 3을 놓칩니다. 예제 2에서는 [6]을 얻습니다.
각 레벨의 마지막 슬롯인 root[2^(d+1)-2]을 읽습니다. 예제 2에서는 인덱스 6에 -1이 있고, 눈에 보이는 노드는 인덱스 3의 8입니다.
자식 위치의 길이 검사를 건너뜁니다. 예제 1에서 3은 마지막 항목이므로 자식 위치 17과 18은 존재하지 않습니다.
각 라운드의 마지막 노드를 유지하면서 오른쪽 자식을 먼저 큐에 넣습니다. 그러면 왼쪽 뷰인 [5, 2, 7, 3]이 수집됩니다.
오른쪽 우선 탐색에서 나중 노드가 이전 노드를 덮어쓰게 하면, 이 방법도 왼쪽 뷰를 반환합니다.

자주 묻는 질문3

이진 트리의 오른쪽 뷰의 시간 복잡도와 공간 복잡도는 무엇인가요?

노드가 n개일 때 시간 복잡도는 O(n)이며, 어떤 해법도 노드를 건너뛸 수 없습니다. 한 레벨의 가장 오른쪽 노드는 어디에나 있을 수 있기 때문입니다. 큐의 공간 복잡도는 너비가 가장 넓은 레벨의 너비인 w에 대해 O(w)이고, 레벨이 h개인 트리에서 오른쪽 우선 순회에 필요한 공간 복잡도는 O(h)입니다.

왼쪽 우선 깊이 우선 탐색으로 이 문제를 해결할 수 있을까요?

네, 첫 번째 값을 유지하는 대신 덮어쓰면 됩니다. 왼쪽 우선 순회는 각 레벨의 노드를 왼쪽에서 오른쪽으로 방문하므로, 각 노드의 값을 해당 깊이에 저장하고 나중에 방문한 노드가 먼저 저장된 값을 덮어쓰게 하세요. 그러면 각 깊이에는 가장 오른쪽에 있는 노드의 값이 남습니다. 여전히 O(n)이지만, 노드마다 한 번씩 씁니다.

여기서는 너비 우선 탐색과 깊이 우선 탐색 중 어느 것을 사용해야 할까요?

둘 다 선형입니다. 너비 우선 탐색은 정의에 따라 한 라운드마다 한 레벨씩 진행합니다. 깊이 우선 탐색은 현재 경로만 유지하므로 너비가 넓은 트리에서 메모리를 절약하며, 재귀 형태는 몇 줄 더 짧습니다.

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

테스트 #1

테스트 #2

테스트 #3

인자

root = [5, 2, 9, 7, 4, -1, 1, -1, 3]

예상 출력

[5, 9, 1, 3]