LeetCode 104 - Maximum Depth of Binary Tree

이진 트리의 최대 깊이를 구하는 Easy 문제다. DFS로 왼쪽과 오른쪽 서브트리를 끝까지 내려간 뒤, 두 경로에서 계산된 깊이 중 큰 값을 반환했다.

문제 링크 & 설명

문제 링크: 104. Maximum Depth of Binary Tree
요약: 이진 트리의 root가 주어졌을 때, root부터 가장 멀리 있는 leaf node까지의 노드 수를 반환하는 문제다.

빈 트리의 깊이는 0이고, root만 있는 트리의 깊이는 1이다. 각 노드에서는 왼쪽과 오른쪽 중 더 깊은 서브트리를 선택하면 현재 트리의 최대 깊이를 구할 수 있다.

접근 방법

재귀 함수는 현재 노드와 지금까지 내려온 깊이를 함께 받는다. 노드가 None이면 더 내려갈 수 없으므로 현재 depth를 반환한다.

if not node:
    return depth

노드가 있다면 왼쪽과 오른쪽 자식으로 이동하면서 depth를 1씩 늘린다. 두 호출이 반환한 값 중 큰 값이 해당 노드 아래에서 도달할 수 있는 최대 깊이다.

left = self.dfs(node.left, depth + 1)
right = self.dfs(node.right, depth + 1)
return max(left, right)

root의 시작 깊이를 0으로 두면 첫 노드를 방문할 때 자식 호출에 1이 전달되고, leaf node의 None 자식에서 해당 leaf까지 포함한 깊이가 반환된다.

트러블 슈팅

깊이를 노드 수로 셀지 간선 수로 셀지에 따라 시작값과 종료 조건이 달라진다. 이 문제는 root부터 leaf까지 포함된 노드 수를 요구하므로 root 호출은 depth 0에서 시작하고, 실제 노드를 지나 자식으로 내려갈 때 1을 더했다.

이 기준에서는 빈 root가 들어오면 첫 호출에서 바로 0을 반환하고, root 하나만 있는 트리는 왼쪽과 오른쪽 None 자식이 각각 1을 반환한다. 두 입력을 함께 확인하면 한 칸 차이로 어긋나는 오류를 막을 수 있다.

복잡도 분석

시간 복잡도: O(n)
- 최대 깊이를 확인하려면 모든 노드를 한 번씩 방문해야 한다.
공간 복잡도: O(h)
- 재귀 호출 스택은 트리 높이만큼 쌓인다. 균형 트리에서는 O(log n)이고, 한쪽으로 치우친 트리에서는 O(n)이다.

구현 코드

from typing import Optional

class Solution:
    def dfs(self, node: Optional[TreeNode], depth: int) -> int:
        if not node:
            return depth

        left = self.dfs(node.left, depth + 1)
        right = self.dfs(node.right, depth + 1)
        return max(left, right)

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return self.dfs(root, 0)

요약 및 회고

각 노드에서 왼쪽과 오른쪽 서브트리의 결과 중 큰 값을 선택하면 최대 깊이를 계산할 수 있다. 구현에서 확인할 부분은 깊이의 기준이었다. root 호출을 0에서 시작하고 실제 노드를 지날 때 값을 늘리면 빈 트리와 단일 노드 트리도 같은 재귀 규칙으로 처리된다.