Boundary Traversal of Binary Tree

Q: 경계 순회의 시간 복잡도는 얼마인가요?

O(n) . 두 가장자리 순회는 각각 하나의 경로를 따르고, 리프 순회는 모든 노드를 한 번씩 방문합니다. 추가 공간은 재귀 또는 스택을 위해 O(h) 입니다.

보통트리 순회

+10

배열 root에는 이진 트리가 레벨 순서로 저장됩니다. 루트는 인덱스 0에 있고, 인덱스 i의 자식은 2i+1(왼쪽)과 2i+2(오른쪽)에 있으며, 빈 자리는 -1로 표시하고 끝에 -1 항목이 추가로 있을 수도 있습니다. 리프는 자식이 없는 노드입니다.

루트부터 시작해 반시계 방향으로 경계 노드들을 반환하세요.

루트.
왼쪽 경계: 위에서 아래 순서로 나열합니다. 루트의 왼쪽 자식부터 시작해, 왼쪽 자식이 있으면 왼쪽 자식으로 이동하고, 없으면 오른쪽 자식으로 이동합니다. 리프에 도달하기 전에 멈춥니다.
모든 리프를 왼쪽에서 오른쪽 순서로 나열합니다.
오른쪽 경계: 아래에서 위 순서로 나열합니다. 루트의 오른쪽 자식부터 시작하며, 왼쪽 경계와 대칭입니다.

어떤 노드도 두 번 나열되지 않으므로, 노드가 하나인 트리에서는 루트만 반환합니다.

함수

boundaryTraversal(root: integer-array) → integer-array

rootinteger-array: 레벨 순서의 이진 트리이며, 빈 자리는 -1로 표시합니다
반환값integer-array: 루트에서 반시계 방향으로 경계 값

제약 조건

1 ≤ root.length ≤ 32767
각 root[i]는 -1이거나 0 ≤ root[i] ≤ 10⁵인 값입니다.
root[0]은 절대 -1이 아니므로 트리에는 노드가 하나 이상 있습니다.
배열은 마지막 노드 뒤에 -1 항목이 더 있는 상태로 끝날 수 있습니다.
빈 자리의 두 자식도 모두 비어 있으며, 깊이는 최대 14입니다.
노드 값은 서로 다릅니다.

예제

입력: root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
출력: [7, 3, 1, 4, 6, 8, 9]
설명: 루트 7 다음의 왼쪽 경계는 3입니다. 그 자식인 1은 리프입니다. 리프는 1, 4, 6, 8입니다. 오른쪽 경계는 9이며, 리프 8 위에 있습니다.

입력: root = [10, 4, -1, -1, 6, -1, -1, -1, -1, 5, 8]
출력: [10, 4, 6, 5, 8]
설명: 4에는 왼쪽 자식이 없으므로 왼쪽 경계는 6으로 바뀐 다음 리프 5에서 멈춥니다. 리프 5, 8이 뒤따릅니다. 루트에는 오른쪽 자식이 없습니다.

후속 질문

경계를 시계 방향으로 나열하려면 어떻게 해야 할까요? 루트, 오른쪽 가장자리를 위에서 아래로, 잎을 오른쪽에서 왼쪽으로, 그런 다음 왼쪽 가장자리를 아래에서 위로 나열하면 됩니다.

힌트

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

3개 중 0개 열림

풀이

정답은 네 부분을 이어 붙입니다. 루트, 왼쪽 가장자리를 따라 내려가는 경로, 왼쪽에서 오른쪽으로 이어지는 리프, 그리고 거꾸로 읽은 오른쪽 가장자리를 따라 내려가는 경로입니다. 연결 지점에서는 가장자리를 끝내는 리프와 리프인 루트를 각각 한 번씩 나열해야 합니다.

세 부분을 각각 살펴보세요

핵심 아이디어

각 경계는 하나의 경로입니다. 루트의 자식부터 시작해 다음 노드가 잎 노드가 되기 전까지 노드를 나열하고, 잎 부분에서 그 잎 노드를 나열합니다. 왼쪽을 오른쪽보다 먼저 방문하는 전위 순회는 잎 노드를 왼쪽에서 오른쪽 순서로 만납니다. 깊이에 관계없이 왼쪽 하위 트리의 모든 노드는 오른쪽 하위 트리의 왼쪽에 있기 때문입니다. 오른쪽 경계를 위에서 아래로 모은 다음 순서를 뒤집어 덧붙입니다.

각 경계는 하나의 경로를 따르고, 잎 노드 순회는 각 노드를 한 번씩 방문합니다. 따라서 시간 복잡도는 O(n)이고, 재귀는 h단계 깊이까지 진행됩니다.

알고리즘

루트에서 시작합니다. 루트가 리프라면 반환합니다.
인덱스 1부터 시작해 노드가 존재하고 리프가 아닌 동안 노드를 추가한 다음 왼쪽 자식으로 이동합니다. 왼쪽 자식이 없으면 오른쪽 자식으로 이동합니다.
인덱스 1과 2에서 왼쪽을 먼저 방문하는 전위 순회로 모든 리프를 추가합니다.
인덱스 2부터 시작해 2단계와 동일하게 하되 오른쪽 자식을 우선하여 노드를 수집합니다.
수집한 노드를 역순으로 추가합니다.

def boundaryTraversal(root):
    n = len(root)

    def real(i):
        return i < n and root[i] != -1

    def is_leaf(i):
        return not real(2 * i + 1) and not real(2 * i + 2)

    result = [root[0]]
    if is_leaf(0):
        return result

    # 1. The left boundary, top-down, stopping before its leaf.
    i = 1
    while real(i) and not is_leaf(i):
        result.append(root[i])
        i = 2 * i + 1 if real(2 * i + 1) else 2 * i + 2

    # 2. Every leaf: a pre-order walk meets them from left to right.
    def add_leaves(i):
        if not real(i):
            return
        if is_leaf(i):
            result.append(root[i])
            return
        add_leaves(2 * i + 1)
        add_leaves(2 * i + 2)

    add_leaves(1)
    add_leaves(2)

    # 3. The right boundary, collected top-down and added bottom-up.
    right = []
    i = 2
    while real(i) and not is_leaf(i):
        right.append(root[i])
        i = 2 * i + 2 if real(2 * i + 2) else 2 * i + 1
    result.extend(reversed(right))
    return result

에지 플래그를 사용한 전위 순회 한 번

핵심 아이디어

각 노드에 플래그를 지정하여 스택에서 한 번의 전위 순회로 순회들을 합칩니다. 왼쪽 경계에는 1, 오른쪽 경계에는 2, 내부에는 0을 지정합니다. 루트의 자식은 각각 1과 2로 시작합니다. 경계 노드는 자신의 쪽에 있는 자식 또는 유일한 자식에게 플래그를 전달하고, 나머지 모든 자식에게는 0을 전달합니다. 두 번째 예시에서는 1이 4에서 6을 거쳐 5로 전달됩니다.

노드가 스택에서 나올 때마다 모든 리프와 1로 표시된 비리프 노드를 추가하고, 2로 표시된 비리프 노드는 모아 마지막에 역순으로 추가합니다. 경계가 왼쪽에 아무것도 없는 곳에서만 오른쪽으로 꺾이기 때문에, 전위 순회에서는 어떤 리프보다도 먼저 모든 왼쪽 경계 노드에 도달합니다.

알고리즘

루트에서 시작합니다. 오른쪽 자식을 플래그 2와 함께 푸시한 다음, 왼쪽 자식을 플래그 1과 함께 푸시합니다.
노드를 팝합니다. 리프이거나 플래그 1을 가진 경우 추가하고, 플래그 2를 가진 비리프 노드는 오른쪽 목록에 추가합니다.
오른쪽 자식을 푸시한 다음, 왼쪽 자식을 푸시합니다. 각 자식에는 규칙에서 지정하는 플래그를 붙입니다.
스택이 비면 오른쪽 목록을 역순으로 추가합니다.

def boundaryTraversal(root):
    n = len(root)

    def real(i):
        return i < n and root[i] != -1

    result = [root[0]]
    right = []  # the right boundary, top-down; it goes on the end reversed
    # Each entry is (index, edge): 1 = left boundary, 2 = right boundary, 0 = inside.
    stack = []
    if real(2):
        stack.append((2, 2))
    if real(1):
        stack.append((1, 1))
    while stack:
        i, edge = stack.pop()
        has_left, has_right = real(2 * i + 1), real(2 * i + 2)
        if not has_left and not has_right:
            result.append(root[i])  # a leaf; pre-order meets them left to right
        elif edge == 1:
            result.append(root[i])  # the left boundary, top-down
        elif edge == 2:
            right.append(root[i])
        # An edge passes to the child on its own side, or to an only child.
        # The right child goes on the stack first, so the left one comes out first.
        if has_right:
            stack.append((2 * i + 2, edge if edge == 2 or not has_left else 0))
        if has_left:
            stack.append((2 * i + 1, edge if edge == 1 or not has_right else 0))
    result.extend(reversed(right))
    return result

함정과 경계 사례

노드를 두 번 나열하는 것. 리프에서 멈추지 않는 가장자리 순회는 예제 1에서 1을 두 번 나열하며, 노드가 하나뿐인 트리에서는 루트를 리프로 다시 나열하면 안 됩니다.
각 레벨의 첫 번째 노드를 왼쪽 경계로 간주하는 것. 루트의 왼쪽 자식이 리프이고 오른쪽 서브트리가 더 깊다면, 더 깊은 레벨은 오른쪽 서브트리의 노드로 시작하지만 왼쪽 경계는 비어 있습니다.
왼쪽 자식만 따라가는 것. 예제 2에서 경계는 4에서 오른쪽 자식인 6으로 이어져야 합니다.
리프를 레벨별로 모으는 것. 그러면 예제 1의 결과는 1, 8, 4, 6이 됩니다.
Lua와 R에서는 2i+1 연산을 위해 노드 인덱스를 0부터 시작하도록 유지하고 root[i + 1]을 읽습니다.

자주 묻는 질문3

이진 트리의 경계 순회란 무엇인가요?

트리의 개요를 반시계 방향으로 나열합니다. 루트, 위에서 아래로 이어지는 왼쪽 가장자리, 왼쪽에서 오른쪽으로 이어지는 잎, 그리고 아래에서 위로 이어지는 오른쪽 가장자리입니다. 가장자리에서는 잎을 제외하므로 어떤 노드도 두 번 나타나지 않습니다.

경계 순회의 시간 복잡도는 얼마인가요?

O(n). 두 가장자리 순회는 각각 하나의 경로를 따르고, 리프 순회는 모든 노드를 한 번씩 방문합니다. 추가 공간은 재귀 또는 스택을 위해 O(h)입니다.

왼쪽 경계는 항상 왼쪽 자식을 따르나요?

아니요. 왼쪽 자식이 있으면 왼쪽 자식으로 이동하고, 그렇지 않으면 오른쪽 자식으로 이동합니다. 왼쪽에서 보이는 가장 바깥쪽 경로입니다. 루트에 왼쪽 자식이 없으면 왼쪽 경계는 비어 있습니다.

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

테스트 #1

테스트 #2

테스트 #3

인자

root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]

예상 출력

[7, 3, 1, 4, 6, 8, 9]