Maximum Depth of Binary Tree

먼저 배열을 어떻게 탐색하는지 살펴보겠습니다. 인덱스 i에 있는 노드의 왼쪽 자식은 2*i+1, 오른쪽 자식은 2*i+2에 있습니다. 자식은 해당 인덱스가 배열 안에 있고 그곳의 값이 -1이 아닐 때만 실제로 존재합니다. [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]에서 루트 5의 자식은 인덱스 1과 2에 있고, 인덱스 1의 8은 왼쪽 인덱스 3이 비어 있으며 오른쪽 인덱스 4에 3이 있습니다. 그리고 그 3의 아래쪽 인덱스 9에는 6이 있습니다.

이제 핵심 아이디어를 살펴보겠습니다. 어떤 노드를 지나는 가장 깊은 경로는 두 하위 트리 중 더 깊은 쪽으로 내려갑니다. 따라서 인덱스 i에 있는 하위 트리의 깊이는 해당 노드의 깊이 1에 2*i+1과 2*i+2에 있는 하위 트리 깊이 중 더 큰 값을 더한 것입니다. 비어 있는 위치의 깊이는 0이며, 여기서 재귀가 끝납니다. 리프의 깊이는 1 + max(0, 0) = 1이 되고, 값은 루트까지 거슬러 올라갑니다.

각 노드는 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 호출 스택에는 현재 경로의 각 레벨마다 프레임이 하나씩 쌓이므로, 깊이가 h일 때 O(h)의 공간을 사용하며 여기서는 최대 14입니다. 이 제한 덕분에 이 문제에서는 재귀를 안전하게 사용할 수 있습니다. 긴 사슬 모양의 포인터 기반 트리라면 같은 코드가 재귀 제한에 도달하게 되며, Python에서 그 제한은 1000개 프레임입니다.

최대 깊이는 트리의 레벨 수이므로, 경로를 따라가는 대신 레벨을 셀 수 있습니다. 큐는 노드를 레벨 순서대로 방문합니다. 루트를 큐에 넣고 시작한 다음, 노드를 꺼낼 때마다 실제 자식 노드를 큐의 뒤에 추가합니다.

레벨을 세려면 큐를 묶음 단위로 처리합니다. 각 묶음을 처리하기 전에 큐에 노드가 몇 개 있는지 확인합니다. 묶음을 처리하는 동안 추가하는 자식 노드는 기존 노드 뒤에 들어가므로, 이 노드들은 정확히 한 레벨에 속합니다. 그 수만큼 노드를 꺼내고 자식 노드를 큐에 넣은 다음, 깊이에 1을 더합니다. 큐가 비면 깊이는 묶음의 개수입니다. 첫 번째 예시에서 묶음은 [5], [8, 1], [3], [6]이므로 답은 4입니다.

각 노드는 큐에 한 번 들어가고 한 번 나옵니다. 시간 복잡도는 O(n)입니다. 큐에는 한 번에 한 레벨의 노드가 들어가므로, 가장 너비가 넓은 레벨의 노드 수를 w라고 할 때 공간 복잡도는 O(w)입니다. 포화 트리에서는 마지막 레벨에 전체 노드의 약 절반이 들어갑니다. 깊이가 14일 때 16383개 중 8192개가 들어갑니다.

재귀 호출을 하나도 하지 않고도 재귀 방식처럼 경로를 따라갈 수 있습니다. 직접 스택을 만들고 각 노드를 깊이와 함께 저장하세요. 노드가 얼마나 깊이 있는지 기억해 주는 다른 정보가 없기 때문입니다. (0, 1) 쌍으로 시작합니다. 루트의 깊이는 1입니다.

쌍을 하나 꺼내 깊이를 지금까지 확인한 최댓값과 비교한 다음, 실제 자식 노드마다 depth + 1을 붙여 스택에 넣습니다. 트리의 모든 노드는 도달 경로의 길이를 담아 정확히 한 번씩 스택에 들어가므로, 꺼낸 쌍 중 깊이가 가장 큰 값이 답입니다. 첫 번째 예시에서는 인덱스 9에 있는 6이 (9, 4)로 스택에 들어가며, 이보다 깊은 쌍은 없습니다.

시간 복잡도는 O(n)입니다. 스택에는 현재 경로를 따라 아직 처리되지 않은 형제 노드가 저장되며, 레벨당 하나 정도이므로 공간 복잡도는 O(h)입니다. 재귀 방식과 같지만 호출 스택이 넘칠 염려가 없습니다. 트리의 깊이가 깊을 수 있을 때 사용할 방법이며, 포인터 기반 트리에도 그대로 적용할 수 있습니다.