Vertical Order Traversal of a Binary Tree
이진 트리는 힙 순서에 따라 배열 root에 저장됩니다. 루트는 인덱스 0에 있고, 인덱스 i의 자식은 2*i+1(왼쪽)과 2*i+2(오른쪽)에 있습니다. -1은 비어 있는 위치를 나타내며, 배열 끝에 추가 -1 항목이 있을 수 있습니다.
루트는 열 0에 있습니다. 왼쪽 자식은 부모보다 한 열 왼쪽에, 오른쪽 자식은 한 열 오른쪽에 있습니다. 왼쪽에서 오른쪽 순서로 각 열에 대한 목록을 하나씩 반환하세요. 각 열 안에서는 노드를 위에서 아래 순서로 나열하고, 같은 열과 깊이에 있는 노드는 값의 오름차순으로 나열하세요.
함수
- rootinteger-array
- 힙 순서로 된 트리이며, 빈 자리는 -1입니다
- 반환값integer-2d-array
- 열마다 값 목록 하나씩, 가장 왼쪽 열부터 각 열의 위에서 아래 순서로
제약 조건
1 ≤ root.length ≤ 32767- 각
root[i]는-1이거나0 ≤ root[i] ≤ 5000을 만족하는 값이며, 같은 값이 두 번 나타나지 않습니다. root[0]은 절대-1이 아니므로 트리에는 노드가 적어도 하나 있습니다.- 배열은 마지막 노드 뒤에 추가적인
-1항목이 올 수 있습니다. - 빈 자리의 두 자식도 모두 비어 있으며, 트리의 레벨은 최대
14개입니다.
예제
- 입력
- root = [5, 2, 9, 4, 7, 1, 6]
- 출력
- [[4], [2], [5, 1, 7], [9], [6]]
- 설명
- 열 0에는 루트
5가 있고, 두 단계 아래에는7과1이 있습니다. 이 두 값은 열과 깊이가 같으므로,7이 더 왼쪽에 있는데도1이7보다 먼저 옵니다.
- 입력
- root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
- 출력
- [[2, 5], [1, 4], [3]]
- 설명
- 열 -1에는 깊이 1의
2와 깊이 3의5(4의 왼쪽 자식)가 있습니다. 열 0에는 루트1과 인덱스 4의4가 있습니다. 열 1에는3만 있습니다.
- 입력
- root = [6, -1, -1]
- 출력
- [[6]]
- 설명
6에는 자식이 없으므로 답은[6]이라는 단일 열입니다.
후속 질문
모든 값은 최대 5000입니다. 이 점을 활용해 비교 정렬을 없애고 O(n + 5000) 시간에 마칠 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
모든 노드에는 열, 깊이, 값이 있습니다. 이러한 세 쌍을 모두 하나의 목록에 담았다면, 답을 어떤 순서로 나열하겠습니까?
너비 우선 탐색은 이미 노드를 위에서 아래로 순서대로 제공합니다. 여러 노드가 같은 열과 레벨을 공유할 때 순서에서 아직 빠진 부분은 무엇인가요?
트리를 한 번에 한 레벨씩 처리합니다. 각 레벨을 열을 기준으로 정렬한 다음 값으로 정렬하고, 각 값을 해당 열의 목록에 추가한 후, 마지막에 가장 작은 열부터 가장 큰 열까지 목록을 읽습니다.
풀이
각 노드에는 column, depth, value라는 세 개의 키가 있습니다. 정답은 이 키들을 기준으로 정렬된 노드이며, 열마다 하나의 목록으로 나타냅니다. column과 depth가 같으면 순회 중 왼쪽에서 오른쪽으로 만나는 순서가 아니라 value를 기준으로 하므로, 모든 노드를 한꺼번에 정렬하거나 너비 우선 탐색의 각 레벨을 정렬해야 합니다.
모든 노드를 기록한 다음 정렬하기
핵심 아이디어
모든 노드를 순서에 상관없이 한 번씩 방문하여 튜플 (열, 깊이, 값)을 기록합니다. 자식 노드로 한 단계 이동하면 깊이가 1 증가하고 열이 왼쪽 또는 오른쪽으로 1만큼 이동합니다. 그런 다음 튜플을 열, 깊이, 값 순으로 정렬합니다. 이제 각 열의 노드가 필요한 순서대로 함께 모입니다. 정렬된 목록을 순회하며 열이 바뀔 때마다 새 내부 목록을 시작합니다.
예제 1에서 열 0의 튜플은 (0, 0, 5), (0, 2, 1), (0, 2, 7) 순으로 정렬됩니다. O(n log n)인 정렬이 O(n)인 순회보다 지배적이며, 튜플은 O(n)의 공간을 차지합니다.
알고리즘
- 스택에 (인덱스 0, 열 0, 깊이 0)을 푸시합니다.
- 노드를 팝하고 (열, 깊이, 값)을 기록한 다음, 실제 자식 각각을 열이
col-1또는col+1이고 깊이가depth+1인 상태로 푸시합니다. - 스택이 비면 튜플을 열, 깊이, 값 순으로 정렬합니다.
- 튜플을 순회하면서 열이 바뀔 때마다 새 목록을 시작합니다.
def verticalTraversal(root):
n = len(root)
entries = [] # (column, depth, value) for every node
stack = [(0, 0, 0)] # (node index, column, depth); the root is never empty
while stack:
i, col, depth = stack.pop()
entries.append((col, depth, root[i]))
for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
if child < n and root[child] != -1:
stack.append((child, child_col, depth + 1))
# Column, then depth, then value: exactly the order of the answer.
entries.sort()
result = []
for k, (col, depth, value) in enumerate(entries):
if k == 0 or col != entries[k - 1][0]:
result.append([]) # a new column starts
result[-1].append(value)
return result각 레벨 안에서 레벨별로 정렬
핵심 아이디어
너비 우선 탐색은 한 번에 한 레벨씩 처리합니다. 각 노드는 처리될 때 자신의 값을 해당 열의 목록에 추가하므로, 각 목록은 이미 위에서 아래 순서이며 깊이를 기준으로 정렬할 필요가 없습니다. 동률은 같은 레벨 안에서만 발생하므로, 해당 레벨을 처리하기 전에 열을 기준으로 정렬하고, 그다음 값으로 정렬합니다.
예제 1에서 레벨 2의 노드는 열 -2, 0, 0, 2 순서로 4, 7, 1, 6에 도달하고, 정렬하면 4, 1, 7, 6이 되므로 열 0은 [5, 1, 7]이 됩니다. 노드가 있는 열은 끊김 없이 이어진 범위를 이루므로, 가장 작은 열과 가장 큰 열만 추적하면 충분합니다.
m개의 노드가 있는 레벨을 정렬하는 데는 O(m log m)의 비용이 듭니다. 완전 이진 트리의 마지막 레벨에는 노드의 약 절반이 있으므로, 최악의 경우에도 여전히 O(n log n)입니다. 공간 복잡도는 O(n)입니다.
알고리즘
- 레벨 하나를 보유한 상태에서 시작합니다(인덱스 0, 열 0).
- 레벨을 열, 그다음 값 기준으로 정렬합니다.
- 해당 순서대로 각 값을 해당 열의 목록에 추가하고, 열이
col-1및col+1인 실제 자식 노드를 모아 다음 레벨에 넣습니다. - 레벨이 비어 있을 때까지 반복하면서 가장 작은 열과 가장 큰 열을 추적합니다.
- 가장 작은 열부터 가장 큰 열 순서로 목록을 반환합니다.
def verticalTraversal(root):
n = len(root)
columns = {} # column -> its values, top to bottom
level = [(0, 0)] # (node index, column) of every node on the current level
while level:
# Every node here has the same depth: order them by column, then value.
level.sort(key=lambda node: (node[1], root[node[0]]))
next_level = []
for i, col in level:
columns.setdefault(col, []).append(root[i])
for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
if child < n and root[child] != -1:
next_level.append((child, child_col))
level = next_level
# The columns that hold a node form one unbroken range.
return [columns[col] for col in range(min(columns), max(columns) + 1)]
함정과 경계 사례
- 같은 열의 값들을 왼쪽에서 오른쪽 순서로 둡니다. 레벨별 정렬을 하지 않은 너비 우선 탐색에서는 예제 1의 열 0에
[5, 7, 1]이 나오며,[5, 1, 7]이 나오지 않습니다. - 정렬 없이 깊이 우선 탐색을 하면서 값을 추가합니다.
[1, 2, 3, -1, 4, -1, -1, -1, -1, -1, 5]에서는 왼쪽 우선 탐색이 열 1에 깊이 1의3보다 먼저 깊이 3의5를 추가합니다. - 열과 값으로 정렬하지만 깊이로는 정렬하지 않습니다. 그러면 예제 1의 열 0은
[1, 5, 7]이 됩니다. - 열을 문자열을 키로 사용해 저장합니다. 텍스트로 정렬하면
"-1"이"-2"보다 앞에 오므로, 0의 왼쪽 열들이 잘못된 순서로 나옵니다.
자주 묻는 질문3
이진 트리의 수직 순회 시간 복잡도는 무엇인가요?
모든 노드를 열, 깊이 및 값 기준으로 정렬하는 데는 O(n log n)의 비용이 들며 O(n) 순회보다 더 큰 비용을 차지합니다. 레벨별로 정렬해도 최악의 경우는 동일합니다. 완전한 트리의 마지막 레벨에 노드의 약 절반이 있기 때문입니다. 공간 복잡도는 O(n)입니다.
정렬 없이 수직 순서 순회를 수행할 수 있나요?
동점이 왼쪽에서 오른쪽 순서로 정렬되는 경우에만 그렇습니다. 그러면 각 값을 해당 열의 목록에 추가하는 너비 우선 탐색으로 O(n) 시간에 답을 구할 수 있습니다. 동점이 값순으로 정렬되도록 하려면 정렬이 필요하지만, 같은 레벨의 노드끼리만 동점일 수 있으므로 레벨 내에서만 정렬하면 됩니다.
수직 순회는 상단 뷰 및 하단 뷰와 어떤 관련이 있나요?
세 가지 모두 같은 열 번호를 기준으로 노드를 그룹화합니다. 위에서 본 뷰는 각 열에서 가장 얕은 노드를 유지하고, 아래에서 본 뷰는 가장 깊은 노드를 유지합니다. 수직 순서 순회는 모든 노드를 유지하며, 같은 레벨에 여러 노드가 있으면 값에 따라 정렬합니다. 반면 뷰는 위치를 기준으로 노드를 선택합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def verticalTraversal(root):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
root = [5, 2, 9, 4, 7, 1, 6]
예상 출력
[[4], [2], [5, 1, 7], [9], [6]]