Binary Tree Level Order Traversal

Q: 이진 트리 레벨 순회 알고리즘의 시간 복잡도는 얼마인가요?

두 솔루션 모두 각 노드를 한 번씩 방문합니다. n 개의 노드에 대해 시간 복잡도는 O(n) 입니다. 답에는 n 개의 값이 들어 있으므로 공간 복잡도는 O(n) 입니다. 그 외에 큐에는 가장 너비가 넓은 레벨의 노드 수만큼, 재귀에는 트리의 높이만큼 공간이 필요합니다.

Q: 너비 우선 탐색에서 한 레벨이 어디서 끝나는지 어떻게 알 수 있나요?

각 라운드가 시작될 때 큐의 크기를 읽고 정확히 그 수만큼 노드를 가져옵니다. 다른 두 가지 방법도 있습니다. 현재 레벨과 다음 레벨을 별도의 목록 두 개에 보관하거나, 각 레벨 뒤에 표시자를 큐에 넣습니다.

Q: 배열은 이미 레벨별로 저장되어 있습니다. 슬라이스 단위로 읽으면 어떨까요?

이 형식에서는 다음과 같이 작동합니다. 루트가 0인 레벨 d 는 인덱스 2^d-1 부터 2^(d+1)-2 까지 채우므로, 범위에 값이 하나도 없을 때까지 각 범위의 비어 있지 않은 값을 수집합니다. 면접에서는 보통 포인터가 있는 노드 객체를 대신 전달하며, 이 형식에도 그대로 적용되는 것은 큐뿐입니다.

보통트리 순회 큐

+10

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

노드 값을 레벨별로 반환하세요. 루트부터 가장 깊은 레벨까지 각 레벨마다 하나의 리스트를 만들고, 각 리스트에는 왼쪽에서 오른쪽 순서로 값을 넣습니다.

함수

levelOrder(tree: integer-array) → integer-2d-array

treeinteger-array: 힙 순서의 트리이며, 빈 위치는 -1로 표시합니다
반환값integer-2d-array: 각 수준마다 값 목록 하나씩, 최상위 수준부터 시작하여 각 목록은 왼쪽에서 오른쪽으로

제약 조건

1 ≤ tree.length ≤ 32767
각 tree[i]는 -1이거나 0 ≤ tree[i] ≤ 1000을 만족하는 값입니다.
tree[0]는 절대로 -1이 아니므로, 트리에는 최소 하나의 노드가 있습니다.
배열은 마지막 노드 뒤에 추가적인 -1 항목이 올 수 있습니다.
빈 자리의 두 자식도 모두 비어 있으며, 깊이는 최대 14입니다.

예제

입력: tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
출력: [[4], [9, 2], [6, 8, 5], [3]]
설명: 인덱스 3은 비어 있으므로 9에는 오른쪽 자식인 6만 있습니다. 세 번째 레벨에는 6, 8, 5가 있고, 인덱스 9에 있는 3은 6 아래 네 번째 레벨에 홀로 있습니다.

입력: tree = [7, -1, -1]
출력: [[7]]
설명: 루트의 두 자식은 모두 -1이므로, 트리는 단일 노드 7로 이루어져 있으며 레벨은 하나입니다.

입력: tree = [1, 3, -1, 5, -1, -1, -1]
출력: [[1], [3], [5]]
설명: 각 노드에는 왼쪽 자식만 있습니다. 인덱스 1에는 3이, 인덱스 3에는 5가 있습니다. 각 레벨에는 값이 하나씩 있으며, 끝에 있는 -1 항목은 아무것도 추가하지 않습니다.

후속 질문

각 레벨을 정렬하지 않고 지그재그 순서로 반환할 수 있나요? 첫 번째는 왼쪽에서 오른쪽으로, 두 번째는 오른쪽에서 왼쪽으로, 이런 식으로요.

힌트

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

3개 중 0개 열림

풀이

각 레벨은 각각 왼쪽에서 오른쪽으로 나열되어야 합니다. 큐를 사용하는 너비 우선 탐색은 노드를 그 순서대로 방문하며, 각 라운드가 시작될 때 큐에는 정확히 한 레벨의 노드만 들어 있으므로 큐의 크기로 가져올 노드 수를 알 수 있습니다. 각 노드의 깊이를 추적하는 깊이 우선 순회도 사용할 수 있습니다.

깊이별로 정렬된 깊이 우선

핵심 아이디어

트리를 깊이 우선으로 순회하면서 각 노드에 깊이를 전달합니다. 루트의 깊이는 0이며, 깊이별로 리스트를 하나씩 유지합니다. 깊이 d에 있는 노드는 리스트 d에 값을 추가하며, 해당 레벨에서 처음 방문한 노드라면 리스트를 생성합니다.

순회는 노드의 왼쪽 서브트리를 마친 다음 오른쪽 서브트리로 들어가므로, 각 리스트의 값은 왼쪽에서 오른쪽 순서로 나옵니다. 같은 레벨에 있는 두 노드 중 경로가 갈라지는 지점에서 왼쪽으로 꺾이는 경로에 있는 노드가 먼저 방문됩니다. 예제 1에서는 방문 순서 4, 9, 6, 3, 2, 8, 5에 따라 [4], [9, 2], [6, 8, 5], [3]이 채워집니다.

각 노드는 한 번씩 방문합니다. 시간 복잡도는 O(n)이며, 재귀 깊이는 트리의 깊이만큼으로 최대 14레벨입니다.

알고리즘

레벨의 빈 목록을 만듭니다.
깊이 0으로 루트를 방문합니다.
깊이 d인 노드 i에서, i가 끝을 지났거나 tree[i]가 -1이면 중단합니다.
d개의 목록만 있다면 빈 목록을 하나 추가합니다. tree[i]를 목록 d에 추가합니다.
깊이 d+1로 2i+1을 방문한 다음 2i+2를 방문합니다.

def levelOrder(tree):
    n = len(tree)
    levels = []

    def visit(i, depth):
        if i >= n or tree[i] == -1:
            return
        if depth == len(levels):  # the first node seen on this level
            levels.append([])
        levels[depth].append(tree[i])
        # Left before right, so every level fills from left to right.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return levels

너비 우선, 라운드마다 한 단계씩

핵심 아이디어

큐에서 노드를 꺼내고 그 자식들을 왼쪽부터 넣습니다. 레벨 d+1은 레벨 d가 나가야만 들어오므로, 노드는 레벨별로 왼쪽에서 오른쪽 순서로 나갑니다.

이 흐름을 레벨별로 나누려면 한 라운드가 시작될 때 큐의 크기를 확인합니다. 이전 레벨은 모두 나갔고 다음 레벨은 아직 들어오지 않았으므로, 큐에는 현재 레벨만 정확히 들어 있습니다. 그만큼의 노드를 하나의 행에 담고, 그 자식들은 다음 라운드까지 기다립니다. 예제 1에서 각 라운드에는 노드가 1개, 2개, 3개, 1개씩 들어갑니다.

각 노드는 큐에 한 번 들어가고 한 번 나옵니다. 시간 복잡도는 O(n)입니다. 큐에는 대략 한 레벨의 노드가 들어가며, 14레벨로 이루어진 완전한 트리의 가장 깊은 레벨에서는 최대 8,192개의 노드가 들어갑니다.

알고리즘

루트의 인덱스 0을 큐에 넣습니다.
큐가 비어 있지 않은 동안 큐의 크기 s를 읽고 빈 행을 시작합니다.
인덱스 s개를 꺼냅니다. 각 인덱스 i에 대해 tree[i]를 행에 추가합니다.
인덱스가 배열의 범위 안에 있고 -1이 아닌 값을 가지면 2i+1을 큐에 넣은 다음 2i+2를 넣습니다.
행을 답에 추가하고 다음 라운드를 시작합니다.

from collections import deque


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

함정과 경계 사례

큐를 비우는 동안 큐의 크기를 읽는 것. while (j < queue.length)에서는 자식 노드가 도착할수록 길이가 늘어나므로, 다음 레벨의 노드가 현재 행에 섞입니다.
왼쪽 자식보다 오른쪽 자식을 먼저 추가하거나 오른쪽 하위 트리를 먼저 방문하는 것. 그러면 예제 1의 두 번째 레벨은 [2, 9]가 됩니다.
경계 검사 child < n을 건너뛰는 것. 가장 깊은 노드의 자식 인덱스는 배열의 끝을 넘어섭니다.
일반 배열 리스트의 맨 앞에서 요소를 제거하는 것. 많은 언어에서 이렇게 하면 매번 큐 전체가 이동합니다. 실제 큐나 head 인덱스를 사용하세요.
-1을 노드로 취급하는 것. -1은 행이나 큐에 들어가지 않습니다. [7, -1, -1]의 결과는 [[7], []]가 아니라 [[7]]입니다.

자주 묻는 질문3

이진 트리 레벨 순회 알고리즘의 시간 복잡도는 얼마인가요?

두 솔루션 모두 각 노드를 한 번씩 방문합니다. n개의 노드에 대해 시간 복잡도는 O(n)입니다. 답에는 n개의 값이 들어 있으므로 공간 복잡도는 O(n)입니다. 그 외에 큐에는 가장 너비가 넓은 레벨의 노드 수만큼, 재귀에는 트리의 높이만큼 공간이 필요합니다.

너비 우선 탐색에서 한 레벨이 어디서 끝나는지 어떻게 알 수 있나요?

각 라운드가 시작될 때 큐의 크기를 읽고 정확히 그 수만큼 노드를 가져옵니다. 다른 두 가지 방법도 있습니다. 현재 레벨과 다음 레벨을 별도의 목록 두 개에 보관하거나, 각 레벨 뒤에 표시자를 큐에 넣습니다.

배열은 이미 레벨별로 저장되어 있습니다. 슬라이스 단위로 읽으면 어떨까요?

이 형식에서는 다음과 같이 작동합니다. 루트가 0인 레벨 d는 인덱스 2^d-1부터 2^(d+1)-2까지 채우므로, 범위에 값이 하나도 없을 때까지 각 범위의 비어 있지 않은 값을 수집합니다. 면접에서는 보통 포인터가 있는 노드 객체를 대신 전달하며, 이 형식에도 그대로 적용되는 것은 큐뿐입니다.

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

테스트 #1

테스트 #2

테스트 #3

인자

tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]

예상 출력

[[4], [9, 2], [6, 8, 5], [3]]