Binary Tree Level Order Traversal

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

너비 우선 및 깊이 우선 해법 모두 각 노드를 한 번씩 방문하므로, 노드가 n 개일 때 실행 시간은 O(n) 입니다. 답 자체에는 n 개의 값이 들어 있으므로 공간 복잡도는 O(n) 입니다. 그 외에 큐에는 최대한 가장 넓은 레벨에 있는 노드 수 정도가 들어가고, 재귀 호출은 트리의 높이만큼 쌓입니다.

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

각 라운드가 시작될 때 큐의 크기를 읽으세요. 그 순간 큐에는 한 레벨의 노드만 정확히 들어 있으므로, 그만큼의 노드를 꺼내면 해당 레벨만 꺼내고 그 이상은 꺼내지 않습니다. 다른 두 가지 방법도 가능합니다. 현재 레벨과 다음 레벨을 별도의 목록에 보관하거나, 각 레벨 뒤에 표시자를 넣으세요.

Q: 깊이 우선 탐색으로 레벨 순서 순회를 할 수 있나요?

네. 각 노드에 깊이를 전달하고 해당 깊이의 목록에 값을 추가하세요. 순회에서 왼쪽 하위 트리를 오른쪽 하위 트리보다 먼저 방문하기만 하면 각 목록은 왼쪽에서 오른쪽 순서로 정렬됩니다. 시간 복잡도도 O(n) 입니다. 너비 우선 탐색은 레벨을 순서대로 생성하므로 이 작업에 더 직접적으로 적합합니다.

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

이 형식에서는 다음이 성립합니다. 레벨 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]]
설명: 루트 4에는 인덱스 1과 2에 자식 9와 2가 있습니다. 인덱스 3은 비어 있으므로 세 번째 레벨에는 6(인덱스 4, 9 아래)이 있고, 그다음 8과 5(인덱스 5와 6, 2 아래)가 있습니다. 인덱스 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 항목은 아무것도 추가하지 않습니다.

제출 시 숨은 테스트 +15개

후속 질문

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

힌트

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

3개 중 0개 열림

풀이

각 레벨은 왼쪽에서 오른쪽 순서로 각각 별도의 목록으로 나와야 합니다. 큐를 사용하는 너비 우선 탐색은 노드를 정확히 그 순서대로 방문합니다. 추가로 필요한 아이디어는 레벨이 끝나는 지점을 아는 것입니다. 각 라운드가 시작될 때 큐에는 현재 레벨의 노드만 모두 들어 있으므로, 큐의 크기로 몇 개의 노드를 꺼내야 하는지 알 수 있습니다. 각 노드의 깊이를 기록하고 왼쪽을 오른쪽보다 먼저 방문한다면 깊이 우선 탐색도 사용할 수 있습니다.

깊이 우선, 깊이별로 정리

핵심 아이디어

먼저 배열에서 이동하는 방법을 살펴보겠습니다. 인덱스 i의 왼쪽 자식은 2i+1에 있고 오른쪽 자식은 2i+2에 있습니다. 자식의 인덱스가 배열의 끝을 벗어나거나 -1을 담고 있으면 해당 자식은 없습니다. 예제 1에서 9(인덱스 1)의 자식은 인덱스 3과 4에 있으며, 각각 -1과 6을 담고 있으므로 9에는 오른쪽 자식만 있습니다.

이제 트리를 깊이 우선으로 순회하면서 각 노드에 깊이를 전달합니다. 루트의 깊이는 0입니다. 깊이마다 리스트를 하나씩 둡니다. 깊이 d인 노드에 도달하면 그 값을 리스트 d에 추가합니다. 지금까지 리스트가 d개뿐이라면 새 레벨의 첫 번째 노드이므로 먼저 새 리스트를 만듭니다.

각 레벨의 값이 왼쪽에서 오른쪽 순서로 나오는 이유는 무엇일까요? 순회는 오른쪽 서브트리로 들어가기 전에 노드의 왼쪽 서브트리 전체를 끝냅니다. 같은 레벨에 있는 두 노드를 생각해 보세요. 루트에서 내려오는 경로가 갈라지는 지점에서 한쪽은 왼쪽으로, 다른 쪽은 오른쪽으로 가며, 순회는 왼쪽 노드에 먼저 도달합니다. 예제 1의 순서는 4, 9, 6, 3, 2, 8, 5이며, 이 순서대로 리스트는 [4], [9, 2], [6, 8, 5], [3]으로 채워집니다.

각 노드는 한 번씩 방문하므로 노드가 n개일 때 시간 복잡도는 O(n)이고, 리스트에는 값이 n개 들어갑니다. 재귀 깊이는 트리의 깊이만큼이며, 여기서는 최대 15레벨입니다. R 버전은 대신 명시적인 스택을 사용합니다. 왼쪽 자식이 먼저 나오도록 오른쪽 자식을 왼쪽 자식보다 먼저 스택에 넣은 다음, split으로 깊이별 값을 묶습니다.

알고리즘

빈 레벨 목록을 만듭니다.
깊이 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의 부모가 큐에서 나올 때 레벨 d+1의 모든 노드가 큐에 들어가므로, 레벨 d의 모든 노드가 나오기 전에 레벨 d+1의 노드가 나오는 일은 없으며, 같은 레벨 안에서는 노드가 왼쪽에서 오른쪽 순서로 나옵니다.

이렇게 하면 레벨 순서대로 값이 하나씩 이어진 결과를 얻습니다. 이를 레벨별로 나누려면 한 라운드가 시작될 때 큐의 크기를 확인합니다. 이 시점의 큐에는 현재 레벨의 노드만 정확히 들어 있습니다. 이전 레벨은 이미 모두 나왔고 다음 레벨은 아직 하나도 들어오지 않았기 때문입니다. 그 수만큼 노드를 꺼내 하나의 리스트에 담습니다. 꺼낸 노드들이 추가하는 자식은 다음 라운드에 속합니다.

예제 1에서 큐는 [4]로 시작합니다. 노드 1개를 꺼내 행 [4]를 만들고, 9, 2가 들어옵니다. 노드 2개를 꺼내 행 [9, 2]를 만들고, 6, 8, 5가 들어옵니다. 노드 3개를 꺼내 행 [6, 8, 5]를 만들고, 3이 들어옵니다. 노드 1개를 꺼내 행 [3]을 만들면 큐가 비게 됩니다.

모든 노드는 큐에 한 번 들어가고 한 번 나오므로 시간 복잡도는 O(n)입니다. 큐에는 최대 한 레벨 정도의 노드가 들어갑니다. 깊이가 14인 완전 트리의 가장 깊은 레벨에는 최대 16384개의 노드가 있습니다. 실제 큐를 사용하거나 헤드 인덱스를 사용하세요. 여러 언어에서는 일반 배열 리스트에서 첫 요소를 꺼내면 그 뒤의 모든 요소가 이동합니다.

알고리즘

루트의 인덱스 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을 값으로 취급하는 경우입니다. 비어 있는 위치는 노드가 아니므로 행에 들어가지도, 큐에 들어가지도 않습니다.
경계 검사를 잊는 경우입니다. 가장 깊은 노드의 자식은 배열의 끝을 넘어갈 수 있으므로, tree[child]를 읽기 전에 child < n을 검사하세요.
빈 레벨을 반환하는 경우입니다. 뒤에 있는 -1 항목에는 노드가 없으므로, [7, -1, -1]의 답은 [[7]]이지 [[7], []]가 아닙니다.

자주 묻는 질문4

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

너비 우선 및 깊이 우선 해법 모두 각 노드를 한 번씩 방문하므로, 노드가 n개일 때 실행 시간은 O(n)입니다. 답 자체에는 n개의 값이 들어 있으므로 공간 복잡도는 O(n)입니다. 그 외에 큐에는 최대한 가장 넓은 레벨에 있는 노드 수 정도가 들어가고, 재귀 호출은 트리의 높이만큼 쌓입니다.

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

각 라운드가 시작될 때 큐의 크기를 읽으세요. 그 순간 큐에는 한 레벨의 노드만 정확히 들어 있으므로, 그만큼의 노드를 꺼내면 해당 레벨만 꺼내고 그 이상은 꺼내지 않습니다. 다른 두 가지 방법도 가능합니다. 현재 레벨과 다음 레벨을 별도의 목록에 보관하거나, 각 레벨 뒤에 표시자를 넣으세요.

깊이 우선 탐색으로 레벨 순서 순회를 할 수 있나요?

네. 각 노드에 깊이를 전달하고 해당 깊이의 목록에 값을 추가하세요. 순회에서 왼쪽 하위 트리를 오른쪽 하위 트리보다 먼저 방문하기만 하면 각 목록은 왼쪽에서 오른쪽 순서로 정렬됩니다. 시간 복잡도도 O(n)입니다. 너비 우선 탐색은 레벨을 순서대로 생성하므로 이 작업에 더 직접적으로 적합합니다.

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

이 형식에서는 다음이 성립합니다. 레벨 d는 인덱스 2^d-1부터 2^(d+1)-2까지를 차지하므로, 각 범위의 비어 있지 않은 값을 모으고 값이 하나도 없는 첫 번째 범위에서 중단하면 됩니다. 하지만 면접에서는 보통 트리가 왼쪽 및 오른쪽 포인터가 있는 노드 객체로 주어지며, 분할할 인덱스는 없습니다. 큐 기반 순회는 그런 형식과 지그재그 순서 또는 오른쪽 뷰와 같은 변형에도 적용할 수 있습니다.

Python

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

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

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

기대값

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