Invert Binary Tree

Q: 이진 트리를 뒤집는 시간 복잡도는 얼마인가요?

각 노드는 한 번씩 방문하므로 시간 복잡도는 O(n) 입니다. 재귀 해법은 깊이가 h 인 트리에서 스택 공간 O(h) 를 사용하고, 큐 기반 해법은 가장 너비가 넓은 레벨에서 O(w) 를 사용합니다. 이 배열 버전에서는 결과 자체가 새 배열이므로 O(n) 이 추가됩니다.

쉬움트리 순회

+10

레벨 순서로 배열 tree에 저장된 이진 트리가 주어집니다. 루트는 인덱스 0에 있고, 인덱스 i에 있는 노드의 자식은 2*i+1(왼쪽)과 2*i+2(오른쪽)에 있으며, -1은 비어 있는 위치를 나타내고, 배열 끝에는 추가 -1 항목이 있을 수 있습니다.

트리를 뒤집으세요. 즉, 모든 노드의 왼쪽 자식과 오른쪽 자식을 서로 바꿔 전체 트리가 거울상으로 되게 하세요. 끝에 -1 항목이 없는 동일한 형식의 뒤집힌 트리를 반환하세요.

함수

invertTree(tree: integer-array) → integer-array

treeinteger-array: 레벨 순서로 표현한 이진 트리이며, 빈 자리는 -1로 표시합니다
반환값integer-array: 후행 -1 항목이 없는, 레벨 순서로 나열한 미러링된 트리

제약 조건

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

예제

입력: tree = [5, 3, 8, 1, 4, -1, 9]
출력: [5, 8, 3, 9, -1, 4, 1]
설명: 루트의 자식인 3과 8이 서로 자리를 바꿉니다. 그 아래에서 3 아래에 있던 1과 4는 4와 1로 바뀌고, 오른쪽 자식인 9만 있던 8은 이제 왼쪽에 자식을 두게 됩니다.

입력: tree = [2, 7, -1, 6]
출력: [2, -1, 7, -1, -1, -1, 6]
설명: 2, 7, 6의 체인은 왼쪽으로 기울어져 있고, 그 거울상은 오른쪽으로 기울어져 있습니다. 7은 인덱스 1에서 인덱스 2로, 6은 인덱스 3에서 인덱스 6으로 이동하므로, 마지막 노드 앞의 빈 자리마다 -1을 넣으면 정답은 입력보다 길어집니다.

입력: tree = [1, -1, -1]
출력: [1]
설명: 단일 노드는 그 자체의 거울입니다. 두 개의 -1 항목은 패딩이며, 답에서는 끝에 있는 모든 -1을 제거합니다.

제출 시 숨은 테스트 +14개

후속 질문

반전된 복사본을 만들지 않고 동일한 인덱스 쌍을 사용하여 트리가 자기 자신의 거울상인지 어떻게 확인할 수 있을까요?

힌트

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

3개 중 0개 열림

풀이

트리를 미러링한다는 것은 모든 노드가 아래쪽 끝까지 자신의 왼쪽 서브트리와 오른쪽 서브트리를 맞바꾸는 것을 의미합니다. 노드 객체를 사용하면 노드마다 한 번씩 맞바꾸면 됩니다. 이 배열 형식에서는 노드의 위치가 인덱스이므로, 두 서브트리를 맞바꾸려면 그 안에 있는 모든 노드를 이동해야 합니다. 새로운 배열에 결과를 만들고 각 노드를 미러링된 인덱스로 바로 복사하면 됩니다. 이를 위해 순회하면서 인덱스 쌍, 즉 노드가 현재 있는 위치와 이동할 위치를 함께 전달합니다.

각 노드를 대칭 인덱스에 배치하는 재귀

핵심 아이디어

먼저 배열을 탐색하는 방법입니다. 인덱스 i에 있는 노드의 왼쪽 자식은 2*i+1에, 오른쪽 자식은 2*i+2에 있습니다. 자식은 인덱스가 배열 범위 안에 있고 해당 위치의 값이 -1이 아닌 경우에만 실제로 존재합니다. [5, 3, 8, 1, 4, -1, 9]에서 루트 5의 자식은 인덱스 1과 2에 있는 3과 8이며, 인덱스 2의 8은 인덱스 5에 왼쪽 자리가 비어 있고 인덱스 6에 9가 있습니다.

이제 대칭으로 바꿔 보겠습니다. 루트는 인덱스 0에 그대로 있습니다. 노드의 왼쪽 서브트리는 대칭으로 바뀐 노드의 오른쪽 서브트리가 되고, 오른쪽 서브트리는 왼쪽 서브트리가 됩니다. 따라서 인덱스 src의 노드가 결과에서 인덱스 dst에 놓인다면, 왼쪽 자식은 2*dst+2에, 오른쪽 자식은 2*dst+1에 놓입니다. place(src, dst)를 작성합니다. 값을 복사한 다음 place(2*src+1, 2*dst+2)와 place(2*src+2, 2*dst+1)을 호출합니다. 빈 자리에 도달하면 즉시 반환합니다. 첫 번째 예에서 인덱스 1의 3은 2에 놓이므로, 왼쪽 자식 1은 6에, 오른쪽 자식 4는 5에 놓입니다.

노드는 레벨이 바뀌지 않으므로 대칭으로 바뀐 인덱스도 기존 노드와 같은 레벨 안에 있습니다. 길이를 완전한 레벨 수에 맞게 올림합니다(1, 3, 7, 15, ...). 그만큼의 자리를 -1로 채운 다음, 끝에 있는 -1 항목을 잘라 냅니다. 두 번째 예에서 길이 4는 7로 올림되므로 인덱스 6의 6이 들어갈 자리가 생깁니다.

각 노드는 한 번씩 배치되고 출력 배열은 한 번 채우고 잘라 내므로, 길이가 n인 배열에서 시간 복잡도는 O(n)입니다. 출력에 O(n)의 메모리가 필요하고 호출 스택에는 O(h)가 필요합니다. 여기서는 최대 14개의 프레임이며, 이 점 덕분에 이 문제에서 재귀를 안전하게 사용할 수 있습니다.

알고리즘

길이를 size = 2^k - 1까지 올림하고, 해당 크기의 출력 배열을 -1로 채우세요.
place(src, dst)를 작성하세요. src가 끝을 벗어났거나 tree[src]가 -1이면 반환하세요.
그렇지 않으면 out[dst] = tree[src]로 설정한 다음, place(2*src+1, 2*dst+2)와 place(2*src+2, 2*dst+1)을 호출하세요.
place(0, 0)을 호출하고, 뒤에 붙은 -1 항목을 제거한 다음 출력을 반환하세요.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size

    def place(src, dst):
        if src >= n or tree[src] == -1:
            return
        out[dst] = tree[src]
        place(2 * src + 1, 2 * dst + 2)  # the left subtree goes to the right
        place(2 * src + 2, 2 * dst + 1)  # the right subtree goes to the left

    place(0, 0)
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

인덱스 쌍 큐를 사용한 너비 우선 탐색

핵심 아이디어

같은 쌍을 재귀 없이도 사용할 수 있습니다. 큐에 (0, 0)을 넣습니다. 루트와 루트가 이동할 위치입니다. 맨 앞에서 (src, dst) 쌍을 꺼내 tree[src]를 out[dst]에 복사하고, 실제 자식마다 목적지를 서로 바꿔 큐에 넣습니다. 왼쪽 자식 2*src+1은 2*dst+2와 짝을 이루고, 오른쪽 자식 2*src+2는 2*dst+1과 짝을 이룹니다.

이것은 전형적인 반복적 역전입니다. 노드 객체를 사용할 때는 큐에서 노드를 꺼내 두 자식을 바꾼 다음 큐에 넣습니다. 여기서는 배열이 두 하위 트리 전체를 한 번에 바꿀 수 없으므로, 대신 목적지 인덱스에 바뀐 결과를 기록합니다. 실제 노드는 각각 한 번씩 큐에 들어가 자신이 속할 정확한 위치를 함께 전달하므로, 결과에는 모든 노드가 거울상 위치에 놓입니다. 첫 번째 예시에서 쌍은 (0, 0), (1, 2), (2, 1), (3, 6), (4, 5), (6, 3) 순서로 나옵니다.

시간 복잡도는 O(n)입니다. 큐에는 최대 한 레벨과 약간의 노드가 들어가므로, 가장 너비가 넓은 레벨의 너비를 w라고 할 때 추가 공간은 O(w)이며, 여기에 O(n) 크기의 출력 공간이 더해집니다. 호출 스택이 넘칠 일이 없으므로, 이 버전은 깊은 포인터 기반 트리에도 변경 없이 적용할 수 있습니다.

알고리즘

길이를 올림하여 정수 레벨 수로 만들고, 그 크기의 출력 배열을 -1로 채웁니다.
쌍 (0, 0)을 큐에 넣습니다.
큐의 맨 앞에서 쌍 (src, dst)를 꺼내고 out[dst] = tree[src]로 설정합니다.
배열 범위 안에 있고 -1이 아닌 각 자식에 대해 (2*src+1, 2*dst+2)와 (2*src+2, 2*dst+1)을 큐에 넣습니다.
큐가 비면 끝에 있는 -1 항목을 제거하고 출력을 반환합니다.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size
    queue = [(0, 0)]  # pairs: index in tree, index of its mirrored spot in out
    head = 0
    while head < len(queue):
        src, dst = queue[head]
        head += 1
        out[dst] = tree[src]
        left, right = 2 * src + 1, 2 * src + 2
        if left < n and tree[left] != -1:
            queue.append((left, 2 * dst + 2))  # the left child goes to the right
        if right < n and tree[right] != -1:
            queue.append((right, 2 * dst + 1))  # the right child goes to the left
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

함정과 경계 사례

거울 변환 자체는 간단히 설명할 수 있습니다. 버그는 배열에서 발생합니다. 배열의 크기와 끝, 그리고 두 항목을 교환할 때 실제로 무엇이 이동하는지가 문제입니다.

tree[2*i+1]과 tree[2*i+2]를 제자리에서 교환하기. 이렇게 하면 두 값은 바뀌지만 그 아래의 서브트리는 바뀌지 않습니다. 첫 번째 예제에서 인덱스 1과 2를 교환하면 1과 4가 8 아래에 매달린 채로 남습니다.
출력을 입력과 같은 길이로 만들기. 두 번째 예제에서 6이 그러듯, 거울 변환된 노드는 입력의 마지막 인덱스를 넘어설 수 있습니다. 출력 크기는 전체 레벨을 담을 수 있도록 설정하세요.
끝부분을 잘라내는 것을 잊기. 패딩된 입력과 거울 변환 결과가 입력보다 일찍 끝나는 트리 모두에서, 정답의 끝에는 -1이 없어야 합니다.
배열 전체를 뒤집기. 이렇게 하면 레벨이 뒤섞여 마지막 리프가 루트가 됩니다.
범위 검사를 건너뛰기. 배열이 마지막 노드 바로 뒤에서 끝날 수 있으므로 자식 인덱스가 입력 범위를 벗어날 수 있습니다.
배열이 1부터 시작하는 Lua와 R에서 오프셋을 혼동하기. 2*i+1 계산에는 인덱스를 0부터 시작하는 기준으로 유지하고 tree[i + 1]을 읽으세요.

자주 묻는 질문4

이진 트리를 뒤집는다는 것은 무엇을 의미하나요?

이진 트리를 반전하면 거울에 비친 모습으로 바뀝니다. 모든 노드에서 왼쪽 하위 트리와 오른쪽 하위 트리가 서로 자리를 바꿉니다. 루트는 그대로 있고, 가장 왼쪽 잎은 가장 오른쪽으로 이동하며, 왼쪽으로 이어진 가지는 오른쪽으로 이어진 가지가 됩니다. 두 번 반전하면 원래 트리로 돌아옵니다.

이진 트리를 뒤집는 시간 복잡도는 얼마인가요?

각 노드는 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 재귀 해법은 깊이가 h인 트리에서 스택 공간 O(h)를 사용하고, 큐 기반 해법은 가장 너비가 넓은 레벨에서 O(w)를 사용합니다. 이 배열 버전에서는 결과 자체가 새 배열이므로 O(n)이 추가됩니다.

재귀 없이 이진 트리를 어떻게 뒤집나요?

큐나 스택을 사용하세요. 루트에서 시작하고, 노드를 꺼낼 때마다 왼쪽 자식과 오른쪽 자식을 서로 바꾼 다음 자식 노드들을 넣으세요. 어떤 순서로 노드를 꺼내든 모든 노드는 한 번씩 자식이 바뀝니다. 배열 형태에서는 대신 인덱스 쌍을 큐에 넣고 각 노드를 대칭 위치에 바로 기록합니다.

이진 트리를 뒤집으면 각 레벨이 반대로 되는 이유는 무엇인가요?

미러링은 모든 곳에서 왼쪽과 오른쪽을 뒤집으므로 각 레벨의 노드가 반대 순서로 나타납니다. 레벨 순서 저장 방식에서는 각 레벨에 해당하는 배열 슬라이스가 뒤집힌다는 뜻입니다. 첫 번째 예의 [1, 4, -1, 9] 슬라이스는 [9, -1, 4, 1]로 바뀝니다. 마지막 레벨을 -1로 채운 뒤 각 레벨을 뒤집는 방법은 이 배열 레이아웃에서만 작동하는 세 번째 O(n) 해법입니다.

Python

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

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

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

기대값

[5, 8, 3, 9, -1, 4, 1]