Balanced Binary Tree

Q: 균형 이진 트리의 시간 복잡도는 얼마인가요?

후위 순회는 각 노드에 한 번씩 방문하므로 시간은 O(n) 이고, 높이가 h 인 트리에서 스택 공간은 O(h) 입니다. 각 노드에서 높이를 다시 계산하면 O(n·h) 의 비용이 들며, 한 줄로 이어진 트리에서는 O(n²) 이 됩니다.

Q: 이진 트리에서 높이 균형이란 무엇을 의미하나요?

모든 노드에서 왼쪽과 오른쪽 하위 트리의 높이 차이는 최대 1 입니다. AVL 트리는 삽입과 삭제 후마다 이 속성을 복원하여 높이를 O(log n) 으로 유지합니다.

쉬움트리 순회 재귀

+10

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

트리가 높이 균형 상태이면 true를 반환하세요. 즉, 모든 노드에서 왼쪽 및 오른쪽 하위 트리의 높이 차이가 최대 1이어야 합니다. 그렇지 않으면 false를 반환하세요. 하위 트리의 높이는 가장 긴 하향 경로에 있는 노드의 수이며, 빈 하위 트리의 높이는 0입니다.

함수

isBalanced(root: integer-array) → boolean

rootinteger-array: 레벨 순서로 표현한 이진 트리이며, 빈 자리는 -1로 표시합니다
반환값boolean: 모든 노드에서 두 하위 트리의 높이 차이가 1 이하이면 true, 그렇지 않으면 false

제약 조건

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

예제

입력: root = [5, 2, 9, -1, -1, 7, 11]
출력: true
설명: 루트의 왼쪽 하위 트리는 단일 노드 2이며, 높이는 1입니다. 오른쪽 하위 트리 9, 7, 11의 높이는 2입니다. 두 높이의 차이는 1이며, 다른 모든 노드는 높이가 같은 두 하위 트리를 가지고 있습니다.

입력: root = [6, 3, 8, 1, -1, -1, 9, 0, -1, -1, -1, -1, -1, -1, 10]
출력: false
설명: 루트의 양쪽 높이는 모두 3이지만, 노드 3은 조건을 만족하지 않습니다. 왼쪽 하위 트리인 1, 0의 높이는 2이고 오른쪽 하위 트리는 비어 있습니다.

입력: root = [4, 2, -1, 1]
출력: false
설명: 루트에는 왼쪽에 높이 2인 2, 1 체인이 있고, 오른쪽에는 높이 0인 것이 없습니다. 차이 2는 너무 큽니다.

후속 질문

명시적인 스택을 사용해 재귀 없이 트리를 확인할 수 있나요?

힌트

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

3개 중 0개 열림

풀이

이 규칙은 모든 노드에 적용되므로, 두 번째 예시에서 3에서 그러하듯 루트가 균형 잡혀 보여도 트리의 아래쪽에서 조건을 만족하지 못할 수 있습니다. 후위 순회는 각 하위 트리의 높이를 한 번씩 계산하고, 실패가 발생하는 즉시 위로 전달하므로 O(n)입니다.

각 노드의 높이를 다시 계산합니다

핵심 아이디어

정의를 코드로 바꿔 보세요. 빈 위치에서 height(i)는 0이고, 그 외의 위치에서는 더 높은 자식보다 1 더 큽니다. 실제 노드마다 두 자식의 높이를 비교하고, 둘의 차이가 1보다 큰 첫 번째 노드가 답을 false로 만듭니다.

각 검사는 해당 노드 아래의 서브트리 전체를 순회하므로, 각 노드는 그 위에 있는 노드마다 한 번씩 순회됩니다. 따라서 O(n·h)입니다. 레벨이 최대 14개라면 노드가 16,383개인 완전 트리도 약 2 × 10^5 단계가 듭니다. 노드가 n개인 사슬은 O(n²)이 듭니다.

알고리즘

인덱스가 끝을 지나거나 -1인 경우 height(i)를 0으로 정의하고, 실제 노드인 경우 1 + max(height(2*i+1), height(2*i+2))로 정의합니다.
실제 노드가 있는 각 인덱스 i를 방문합니다.
height(2*i+1)과 height(2*i+2)의 차이가 1보다 크면 false를 반환합니다.
실패 없이 루프가 끝나면 true를 반환합니다.

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

    def height(i):
        # The number of nodes on the longest downward path from index i.
        if i >= n or root[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    # Check every real node, measuring both subtrees from scratch.
    for i in range(n):
        if root[i] != -1 and abs(height(2 * i + 1) - height(2 * i + 2)) > 1:
            return False
    return True

높이를 반환하거나 실패를 보고하는 한 번의 후위 순회

핵심 아이디어

노드에서의 검사는 두 하위 트리의 높이를 필요로 하며, 이 높이는 노드가 자신의 높이를 반환할 때도 필요합니다. 따라서 후위 순회 한 번으로 둘 다 구합니다. 각 호출은 두 자식의 처리가 끝난 후 해당 하위 트리의 높이를 반환합니다.

하위에서 발생한 실패도 위로 전달되어야 합니다. 실제 높이는 음수가 될 수 없으므로 -1을 사용합니다. 자식이 -1을 반환했거나 자식들의 높이 차이가 1보다 크면 호출은 -1을 반환합니다. 두 번째 예시에서 3은 높이 2와 0을 확인하고 -1을 반환하며, 루트는 오른쪽을 방문하지 않고 이를 그대로 전달합니다.

각 노드는 한 번만 방문하므로 시간 복잡도는 O(n)이고, 스택의 호출 수는 O(h)입니다.

알고리즘

check(i)를 작성하세요. 끝을 벗어난 인덱스이거나 -1이면 0을 반환하세요.
left = check(2*i+1)을 계산하세요. 결과가 -1이면 -1을 반환하세요.
right = check(2*i+2)를 계산하세요. 결과가 -1이거나 left와 right의 차이가 1보다 크면 -1을 반환하세요.
그렇지 않으면 1 + max(left, right)를 반환하세요.
check(0)이 -1이 아닌지 반환하세요.

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

    def check(i):
        # The height of the subtree at index i, or -1 if it is not balanced.
        if i >= n or root[i] == -1:
            return 0
        left = check(2 * i + 1)
        if left == -1:
            return -1
        right = check(2 * i + 2)
        if right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return check(0) != -1

함정과 경계 사례

루트만 확인하는 경우. 두 번째 예시에서는 루트의 양쪽 하위 트리 높이가 모두 3이지만, 노드 3의 높이 차이는 2입니다.
가장 얕은 리프와 가장 깊은 리프를 비교하는 경우. 높이가 6인 가장 작은 균형 트리에는 깊이 4와 6에 리프가 있으며, 트리의 모든 노드가 조건을 만족합니다.
위로 올라가는 과정에서 실패를 놓치는 경우. 자식이 -1을 반환하고 부모가 1 + max(-1, 2)를 계산하면, 실패가 다시 높이로 바뀝니다.
배열 길이를 높이로 사용하는 경우. 뒤에 붙은 -1 항목 때문에 배열이 트리의 깊이보다 길어집니다.
Lua와 R에서는 배열이 1부터 시작합니다. 2*i+1을 위해 노드 인덱스는 0부터 시작하도록 유지하고 root[i + 1]을 읽으세요.

자주 묻는 질문3

균형 이진 트리의 시간 복잡도는 얼마인가요?

후위 순회는 각 노드에 한 번씩 방문하므로 시간은 O(n)이고, 높이가 h인 트리에서 스택 공간은 O(h)입니다. 각 노드에서 높이를 다시 계산하면 O(n·h)의 비용이 들며, 한 줄로 이어진 트리에서는 O(n²)이 됩니다.

이진 트리에서 높이 균형이란 무엇을 의미하나요?

모든 노드에서 왼쪽과 오른쪽 하위 트리의 높이 차이는 최대 1입니다. AVL 트리는 삽입과 삭제 후마다 이 속성을 복원하여 높이를 O(log n)으로 유지합니다.

완전 이진 트리는 항상 균형이 잡혀 있나요?

맞습니다. 완전 이진 트리의 모든 레벨은 마지막 레벨을 제외하면 꽉 차 있고, 마지막 레벨은 왼쪽부터 채워지므로 어떤 노드에서든 두 하위 트리의 높이 차이는 최대 1입니다. 그 역은 성립하지 않습니다. 균형 이진 트리는 마지막 레벨의 왼쪽에 빈자리가 있을 수 있습니다.

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

테스트 #1

테스트 #2

테스트 #3

인자

root = [5, 2, 9, -1, -1, 7, 11]

예상 출력

true