Maximum Depth of Binary Tree
레벨 순서로 배열 tree에 저장된 이진 트리가 주어집니다. 루트는 인덱스 0에 있고, 인덱스 i에 있는 노드의 자식은 2*i+1(왼쪽)과 2*i+2(오른쪽)에 있으며, -1은 빈 위치를 나타내고, 배열 끝에 추가 -1 항목이 있을 수 있습니다. 트리의 최대 깊이를 반환하세요. 최대 깊이는 루트에서 리프까지 이어지는 가장 긴 경로에 있는 노드의 수입니다.
함수
- treeinteger-array
- 레벨 순서로 표시한 이진 트리이며, 빈 위치는 -1로 나타냅니다
- 반환값integer
- 루트에서 리프까지의 가장 긴 경로에 있는 노드 수
제약 조건
1 ≤ tree.length ≤ 32767- 각
tree[i]는-1이거나0 ≤ tree[i] ≤ 1000을 만족하는 값입니다. tree[0]은 절대-1이 아니므로 트리에는 노드가 적어도 하나 있습니다.- 배열은 마지막 노드 뒤에 추가
-1항목이 있을 수 있습니다. - 빈 자리의 두 자식도 모두 비어 있으며, 깊이는 최대
14입니다.
예제
- 입력
- tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
- 출력
- 4
- 설명
- 가장 긴 경로는
5,8,3,6(인덱스0,1,4,9)이며, 노드 4개를 포함합니다.1을 거치는 경로는 노드 2개를 지난 뒤 끝납니다.
- 입력
- tree = [7, -1, -1]
- 출력
- 1
- 설명
- 두 개의
-1항목은 루트의 비어 있는 자식 자리입니다. 루트만으로 노드 하나로 이루어진 경로이므로 깊이는1이지0이 아닙니다.
- 입력
- tree = [2, -1, 9, -1, -1, -1, 4]
- 출력
- 3
- 설명
- 루트
2에는 왼쪽 자식이 없습니다. 인덱스2에 있는 오른쪽 자식9의 오른쪽 자식은 인덱스6에 있는4이며, 경로는 노드 3개로 이루어져 있습니다.
후속 질문
가장 긴 루트-리프 경로의 길이와 함께 그 경로에 있는 값들을 어떻게 반환할 수 있을까요? 가장 긴 경로가 여러 개라면 어느 경로를 반환하시겠어요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
루트를 생각해 보세요. 왼쪽 하위 트리의 깊이와 오른쪽 하위 트리의 깊이를 알고 있다면, 전체 트리의 깊이는 얼마일까요?
루트에
1을 더한 값과 두 하위 트리 깊이 중 더 큰 값이며, 비어 있는 위치의 깊이는0입니다. 같은 규칙이 모든 노드에 적용되므로, 각 노드의 깊이를 아는 순회를 통해 답을 찾을 수 있습니다.루트의 깊이를 1로 시작해 노드 인덱스와 깊이로 이루어진 쌍을 스택에 저장합니다. 쌍을 꺼내 가장 큰 깊이를 기억하고, 배열 안에 있고
-1이 아닌 각 자식을 깊이에 1을 더해2*i+1과2*i+2에 넣습니다.
풀이
깊이는 가장 긴 분기에 따라 정해지며, 모든 노드를 방문하지 않고는 어느 분기가 가장 긴지 알 수 없습니다. 따라서 각 노드에서 얼마나 깊이 들어왔는지 파악하는 전체 순회가 한 번 필요합니다. 재귀, 레벨별 너비 우선 탐색, 직접 스택을 사용하는 깊이 우선 탐색은 각각 한 번의 순회로 이를 수행합니다.
두 하위 트리에서의 재귀
핵심 아이디어
자식 위치는 해당 인덱스가 배열 내부에 있고 값이 -1이 아닐 때 실제로 존재합니다. 노드를 통과하는 가장 깊은 경로는 더 깊은 하위 트리로 내려가므로, 인덱스 i에서의 깊이는 해당 노드에 대한 1에 2*i+1과 2*i+2에서의 깊이 중 큰 값을 더한 것입니다. 빈 위치의 깊이는 0이며, 이 값이 재귀를 끝냅니다. 리프 노드의 깊이는 1 + max(0, 0) = 1이고, 값은 루트까지 거슬러 올라갑니다.
각 노드는 한 번씩 방문합니다. 호출 스택에는 현재 경로의 레벨마다 프레임이 하나씩 쌓이며, O(h)이고 여기서는 최대 14입니다.
알고리즘
depth(i)를 작성하세요:i가 배열의 끝을 지났거나tree[i]가-1이면0을 반환합니다.- 그렇지 않으면
1 + max(depth(2*i+1), depth(2*i+2))를 반환합니다. depth(0)을 반환합니다.
def maxDepth(tree):
def depth(i):
# An index past the end or a -1 is an empty spot: depth 0.
if i >= len(tree) or tree[i] == -1:
return 0
return 1 + max(depth(2 * i + 1), depth(2 * i + 2))
return depth(0)너비 우선 탐색, 레벨별로
핵심 아이디어
최대 깊이는 레벨의 수이므로, 경로를 따라가는 대신 레벨을 세면 됩니다. 큐는 노드를 레벨 순서대로 방문합니다. 각 묶음을 처리하기 전에 큐의 크기를 확인하세요. 묶음을 처리하는 동안 추가하는 자식 노드는 기존 노드 뒤에 들어가므로, 큐에 있는 노드는 정확히 한 레벨에 해당합니다. 각 묶음마다 깊이에 1을 더합니다. 첫 번째 예시의 묶음은 [5], [8, 1], [3], [6]이므로 답은 4입니다.
큐에는 한 번에 한 레벨의 노드가 들어 있으며, 가장 너비가 넓은 레벨을 기준으로 O(w)입니다. 깊이가 14인 완전 트리에서는 16383개 노드 중 8192개에 해당합니다.
알고리즘
- 루트 인덱스
0을 큐에 넣고depth = 0으로 설정합니다. - 큐가 비어 있지 않은 동안
depth에1을 더하고 큐의 크기를 읽습니다. - 그 개수만큼 인덱스를 꺼냅니다. 각 인덱스에 대해 배열 범위 안에 있고
-1이 아닌 자식 인덱스2*i+1과2*i+2를 큐에 넣습니다. - 큐가 비면
depth를 반환합니다.
from collections import deque
def maxDepth(tree):
n = len(tree)
queue = deque([0])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)): # exactly the nodes of this level
i = queue.popleft()
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
queue.append(child)
return depth명시적 스택을 사용한 깊이 우선 탐색
핵심 아이디어
노드의 깊이가 얼마나 되는지 기억해 주는 다른 것이 없으므로, 노드 인덱스와 깊이로 이루어진 쌍을 직접 스택에 보관하세요. 루트를 깊이 1로 하여 (0, 1)부터 시작합니다. 각 노드는 자신에게 도달하는 경로의 길이를 담아 한 번씩 푸시되므로, 팝한 깊이 중 가장 큰 값이 정답입니다. 첫 번째 예에서는 6이 (9, 4)로 푸시됩니다.
스택에는 레벨당 대기 중인 형제 노드가 하나 정도 저장되며, O(h)입니다. 오버플로될 호출 스택은 없습니다. 같은 코드는 깊이에 상관없이 포인터 기반 트리에서 작동합니다.
알고리즘
(0, 1)을 스택에 넣고best = 0으로 설정합니다.(i, depth)쌍을 꺼내고best를best와depth중 더 큰 값으로 설정합니다.- 배열 범위 안에 있고
-1이 아닌 각 자식 인덱스2*i+1과2*i+2를depth + 1과 함께 스택에 넣습니다. - 스택이 빌 때까지 반복한 다음
best를 반환합니다.
def maxDepth(tree):
n = len(tree)
best = 0
stack = [(0, 1)] # (node index, depth of that node); the root is never empty
while stack:
i, depth = stack.pop()
best = max(best, depth)
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
stack.append((child, depth + 1))
return best
함정과 경계 사례
- 노드 대신 간선의 수를 세는 경우.
[7, -1, -1]의 깊이는0이 아니라1입니다. - 범위 검사를 건너뛰는 경우. 첫 번째 예시에서 인덱스 9의
6의 자식 인덱스는 19와 20이며, 배열의 끝을 벗어납니다.tree[child]를 읽기 전에child < n인지 확인하세요. - 배열의 길이로 깊이를 계산하는 경우. 뒤에 붙은
-1항목은 노드가 없는 레벨까지 이어집니다.[7, -1, -1]의 길이는 3이지만 깊이는 1입니다. - 배치 루프 안에서 큐의 크기를 읽는 경우. 배치 처리 중 추가되는 자식 때문에 크기가 바뀌므로, 먼저 저장하세요.
- 배열이 1부터 시작하는 Lua와 R에서 오프셋을 혼동하는 경우. 노드 인덱스는
2*i+1에 맞게 0부터 시작하도록 유지하고,tree[i + 1]을 읽으세요.
자주 묻는 질문3
이진 트리의 최대 깊이의 시간 복잡도는 무엇인가요?
모든 접근 방식은 각 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 깊이 우선 방식은 현재 경로를 위해 O(h)의 추가 공간을 사용하며, 여기서 h는 깊이입니다. 너비 우선 방식은 가장 너비가 넓은 레벨을 위해 O(w)의 공간을 사용하며, 이는 완전한 트리에서 노드의 약 절반에 해당합니다.
이진 트리의 최대 깊이를 구할 때 DFS와 BFS 중 무엇을 사용해야 할까요?
둘 다 O(n) 시간에 실행됩니다. 깊이 우선 탐색은 코드가 더 짧고 깊이에 비례하는 메모리를 사용하므로, 너비가 넓고 깊이가 얕은 트리에 적합합니다. 너비 우선 탐색은 레벨을 직접 세고 가장 너비가 넓은 레벨에 비례하는 메모리를 사용하므로, 깊이가 깊고 너비가 좁은 트리에 적합합니다. 최소 깊이를 구할 때는 첫 번째 리프에서 멈출 수 있으므로 BFS가 더 효율적입니다.
이진 트리의 깊이와 높이는 어떻게 다른가요?
노드의 깊이는 루트에서 해당 노드까지 내려가는 단계 수를 세고, 높이는 해당 노드에서 가장 깊은 리프까지 내려가는 단계 수를 셉니다. 트리의 최대 깊이는 루트의 높이와 같습니다. 이 문제에서는 노드 수를 세므로 노드 하나의 깊이는 1입니다. 간선을 세면 그보다 1 적습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def maxDepth(tree):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
예상 출력
4