Binary Tree Zigzag Level Order Traversal

+10

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

노드 값을 지그재그 순서로 레벨별로 반환하세요. 루트 레벨은 왼쪽에서 오른쪽으로, 다음 레벨은 오른쪽에서 왼쪽으로, 이후 가장 깊은 레벨까지 번갈아가며 진행합니다. 이를 나선형 레벨 순회라고도 합니다.

함수

zigzagLevelOrder(root: integer-array) → integer-2d-array

rootinteger-array: 힙 순서로 된 트리이며, 빈 위치에는 -1을 사용합니다
반환값integer-2d-array: 레벨마다 값 목록 하나씩, 최상위 레벨부터 시작하여 왼쪽에서 오른쪽, 오른쪽에서 왼쪽 순으로 번갈아 진행

제약 조건

1 ≤ root.length ≤ 32767
각 root[i]는 -1이거나 0 ≤ root[i] ≤ 10⁴인 값입니다.
노드 값은 서로 다릅니다.
root[0]은 절대 -1이 아니므로, 트리에는 노드가 적어도 하나 있습니다.
배열은 마지막 노드 뒤에 추가 -1 항목이 있을 수 있습니다.
비어 있는 위치의 두 자식도 모두 비어 있으며, 트리의 레벨은 최대 14개입니다.

예제

입력: root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
출력: [[8], [5, 12], [1, 9, 14], [11, 2, 4]]
설명: 왼쪽에서 오른쪽으로 읽으면 레벨은 8; 12, 5; 1, 9, 14; 4, 2, 11입니다. 레벨 1과 3은 역방향으로 진행됩니다: [5, 12] 및 [11, 2, 4].

입력: root = [1, 2, 3, 4, 5, 6, 7, -1, -1]
출력: [[1], [3, 2], [4, 5, 6, 7]]
설명: 세 단계로 이루어진 전체 트리입니다. 중간 단계는 [3, 2]로 뒤집히고, 세 번째 단계는 다시 왼쪽에서 오른쪽으로 진행됩니다. 뒤에 있는 두 개의 -1 항목은 4의 비어 있는 자식 위치입니다.

후속 질문

모든 값을 뒤집거나 두 번째 스택을 사용하지 않고 각 행의 최종 위치에 바로 넣을 수 있나요?

풀이

레벨은 일반적인 너비 우선 탐색에서 나옵니다. 새로운 부분은 방향입니다. 레벨마다 번갈아가며 순서가 뒤집힙니다. 레벨을 만든 다음 홀수 번째 행을 뒤집거나, 각 레벨을 스택에 담으세요. 그러면 푸시한 순서의 반대로 항목을 돌려받습니다.

레벨 순서로, 그런 다음 한 레벨씩 건너뛰며 역순으로

핵심 아이디어

라운드마다 한 레벨씩 처리하는 큐는 각 레벨의 노드를 왼쪽에서 오른쪽으로 반환합니다. 루트를 0으로 하여 레벨에 번호를 매기면, 지그재그 순회는 홀수 레벨을 오른쪽에서 왼쪽으로 읽으므로 해당 행만 뒤집으면 됩니다.

탐색은 각 노드를 한 번씩 방문하고 각 뒤집기 과정은 각 값을 한 번씩 더 처리하므로, 시간 복잡도는 O(n)입니다.

알고리즘

인덱스 0으로 큐를 시작합니다.
각 라운드에서 큐의 길이 s를 저장하고, s개의 인덱스를 큐에서 꺼내 새 행에 넣은 다음, 각 인덱스의 기존 자식 노드를 왼쪽부터 오른쪽 순서로 큐에 넣습니다.
답에 이미 홀수 개의 행이 있으면 해당 행을 뒤집습니다.
행을 추가하고 큐가 빌 때까지 계속합니다.

from collections import deque


def zigzagLevelOrder(root):
    n = len(root)
    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(root[i])
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and root[child] != -1:
                    queue.append(child)
        if len(levels) % 2 == 1:  # levels 1, 3, 5, ... read from right to left
            row.reverse()
        levels.append(row)
    return levels

두 개의 스택

핵심 아이디어

현재 레벨을 레벨을 읽는 방향으로 꺼내는 스택에 저장하고, 꺼낸 각 노드의 자식 노드를 두 번째 스택에 넣습니다. 현재 스택이 비면 두 번째 스택에 다음 레벨이 들어 있습니다.

넣는 순서가 이 방식을 성립하게 합니다. 왼쪽에서 오른쪽으로 꺼낼 때는 각 노드의 왼쪽 자식, 오른쪽 자식 순서로 넣습니다. 그러면 가장 오른쪽 노드의 오른쪽 자식이 마지막에 들어가므로 다음 레벨은 오른쪽 끝에서 꺼내집니다. 오른쪽에서 왼쪽으로 꺼낼 때는 오른쪽 자식, 왼쪽 자식 순서로 넣습니다. 그러면 가장 왼쪽 노드의 왼쪽 자식이 마지막에 들어갑니다.

예제 1: 8을 꺼내고 12, 5를 넣습니다. 5, 12를 꺼낸 다음, 5에서 14를, 12에서 9, 1을 넣습니다. 1, 9, 14를 꺼낸 다음, 9에서 4, 2를, 14에서 11을 넣습니다. 11, 2, 4를 꺼냅니다.

각 노드는 한 번씩 들어가고 꺼내집니다. 시간 복잡도는 O(n)이며, 역순으로 바꾸는 과정이 필요하지 않습니다.

알고리즘

루트의 인덱스 0을 스택에 넣고 왼쪽에서 오른쪽으로 읽기 시작합니다.
스택이 비어 있지 않은 동안 모든 인덱스를 꺼내 새 행에 넣고, 꺼낸 각 노드의 기존 자식들을 두 번째 스택에 넣습니다. 왼쪽에서 오른쪽으로 읽을 때는 왼쪽 자식 다음에 오른쪽 자식을, 그렇지 않을 때는 오른쪽 자식 다음에 왼쪽 자식을 넣습니다.
행을 답에 추가합니다.
두 번째 스택을 현재 스택으로 지정하고, 방향을 뒤집은 다음 반복합니다.

def zigzagLevelOrder(root):
    n = len(root)
    levels = []
    current = [0]  # a stack of node indexes; the root is never empty
    left_to_right = True
    while current:
        row = []
        upcoming = []  # the next level, pushed while this one pops
        while current:
            i = current.pop()
            row.append(root[i])
            # Push so that the next level pops out in its own direction.
            if left_to_right:
                children = (2 * i + 1, 2 * i + 2)
            else:
                children = (2 * i + 2, 2 * i + 1)
            for child in children:
                if child < n and root[child] != -1:
                    upcoming.append(child)
        levels.append(row)
        current = upcoming
        left_to_right = not left_to_right
    return levels

함정과 경계 사례

자식 노드가 하나의 큐에 들어가는 순서를 뒤집는 것. 형제 노드의 순서는 바뀌지만 부모 노드의 순서는 유지됩니다. 예제 1의 세 번째 레벨은 [9, 1, 14]가 됩니다.
레벨을 1부터 세는 것. 뒤집을 때마다 레벨이 하나씩 어긋나며, 예제 1의 결과는 [[8], [12, 5], [14, 9, 1], [4, 2, 11]]이 됩니다.
두 스택 방식의 모든 레벨에서 같은 push 순서를 사용하는 것. 그러면 예제 1의 세 번째 레벨에서 [9, 1, 14]가 pop됩니다.
아직 pop하는 중인 스택에 자식 노드를 push하는 것. 자식 노드가 부모 레벨의 나머지 노드보다 먼저 나옵니다.
행을 뒤집는 대신 정렬하는 것. 예제 1의 마지막 레벨은 [11, 2, 4]여야 하는데, 어떤 정렬로도 이 결과를 얻을 수 없습니다.

자주 묻는 질문3

지그재그 순회와 레벨 순회는 어떤 차이가 있나요?

두 방식 모두 같은 노드를 방문합니다. 레벨 순회는 각 레벨을 왼쪽에서 오른쪽으로 읽고, 지그재그 순회는 루트 바로 아래 레벨부터 시작해 한 레벨씩 건너뛰며 오른쪽에서 왼쪽으로 읽습니다. 둘 다 O(n) 시간에 실행됩니다.

지그재그 순회는 트리의 나선형 순회와 같은가요?

네, 두 이름은 같은 순회를 나타냅니다. 일부 글에서는 오른쪽 대신 왼쪽에서 두 번째 수준을 시작하는데, 이 경우 뒤집기가 한 수준씩만 이동합니다. 여기서는 루트 수준이 왼쪽에서 오른쪽으로 진행되고, 다음 수준은 오른쪽에서 왼쪽으로 진행됩니다.

덱으로 지그재그 레벨 순회를 할 수 있나요?

네. 데크의 각 레벨을 왼쪽에서 오른쪽 순서로 유지하세요. 왼쪽에서 오른쪽으로 진행하는 레벨에서는 앞에서 노드를 가져와 자식 노드를 왼쪽 자식부터 오른쪽 자식 순으로 뒤에 추가하세요. 오른쪽에서 왼쪽으로 진행하는 레벨에서는 뒤에서 노드를 가져와 자식 노드를 오른쪽 자식부터 왼쪽 자식 순으로 앞에 추가하세요. 라운드가 시작될 때 가져올 노드의 개수가 여전히 해당 레벨을 나타냅니다.

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

테스트 #1

테스트 #2

테스트 #3

인자

root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]

예상 출력

[[8], [5, 12], [1, 9, 14], [11, 2, 4]]