LeetCode

LeetCode 104 Maximum Depth of Binary Tree 풀이: 반복형 DFS

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

이진 트리의 왼쪽·오른쪽 서브트리 깊이를 비교해 가장 긴 경로를 구하는 트리 순회 문제다. 트리 자료구조를 순회하며 자식 깊이를 계산해야 하므로 Level 3으로 판단했다.

1. 문제 요약

주어진 이진 트리의 루트부터 가장 먼 리프 노드까지 이어지는 경로의 길이를 반환한다. 깊이는 간선 수가 아니라 경로에 포함된 노드 수로 계산한다.

예를 들어 루트에서 리프까지 노드가 3개라면 최대 깊이는 3이다. 빈 트리는 깊이가 0이고, 자식이 없는 루트 하나만 있는 트리는 깊이가 1이다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

트리 구조와 깊이 기록

어떤 노드에서 시작하는 트리의 깊이는 현재 노드 1개와 두 서브트리 중 더 깊은 쪽의 깊이를 더한 값이다.

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

None 노드의 깊이는 0으로 두면 리프의 자식까지 자연스럽게 처리할 수 있다. 일반적인 재귀 DFS로 표현할 수 있지만, 노드가 한쪽으로 길게 이어진 경우 Python 재귀 깊이 제한에 걸릴 수 있으므로 제출 코드는 명시적인 스택을 사용하는 반복형 DFS로 작성했다.

스택 상태와 깊이의 의미

스택의 (node, depth)는 해당 노드까지 포함한 경로의 노드 수를 함께 보관하는 상태다. 루트가 1에서 시작하고 자식으로 내려갈 때만 1을 더하므로, 스택에서 꺼낸 값 자체가 그 노드의 노드 기준 깊이다. None은 스택에 넣지 않기 때문에 빈 트리는 0으로 남고, 리프의 깊이는 간선 수보다 1 큰 값으로 기록된다. 모든 노드를 꺼낼 때 이 깊이의 최댓값을 갱신하면 어느 쪽 서브트리의 경로도 빠지지 않는다.

3. 문제 해결 코드 (Python)

class Solution:
    def maxDepth(self, root: 'TreeNode') -> int:
        if root is None:
            return 0

        stack = [(root, 1)]
        answer = 0

        while stack:
            node, depth = stack.pop()
            answer = max(answer, depth)

            if node.left is not None:
                stack.append((node.left, depth + 1))
            if node.right is not None:
                stack.append((node.right, depth + 1))

        return answer

모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(V)다. V는 노드 수다. 스택에는 최대 O(V)개의 노드가 들어갈 수 있으므로 공간 복잡도는 O(V)이며, 균형 잡힌 트리에서는 실제 스택 사용량이 트리 높이에 비례한다.

4. 오답 접근과 반례

깊이를 간선 수로 계산하면 노드 수를 요구하는 문제와 결과가 달라진다. 단일 노드 트리에서는 간선이 0개지만 문제의 최대 깊이는 노드 하나를 포함한 1이다.

왼쪽 서브트리만 따라가거나 오른쪽 서브트리만 따라가면 반대쪽에 더 깊은 경로가 있는 경우를 놓친다. 루트의 왼쪽 깊이가 1이고 오른쪽으로 두 단계 더 이어진다면 전체 답은 왼쪽 깊이가 아니라 오른쪽 깊이를 기준으로 계산해야 한다.

복사해 실행할 테스트

로컬 실행 시 아래 TreeNode 보조 클래스를 풀이 코드보다 먼저 두고 assert를 뒤에 붙인다. 빈 트리와 깊이가 있는 트리를 검사한다.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

solver = Solution()
assert solver.maxDepth(None) == 0
root = TreeNode(1, TreeNode(2, TreeNode(3)), TreeNode(4))
assert solver.maxDepth(root) == 3

5. 공식 예제와 추가 검증

LeetCode 공식 예제 2개를 Python 3.12.4에서 테스트용 TreeNode 클래스로 재현해 검증했다.

예제 기대 출력 확인 결과
[3,9,20,null,null,15,7] 3 통과
[1,null,2] 2 통과

추가 검증 1: 빈 트리

입력: root = None
기대 출력: 0
확인 결과: 통과
검증 목적: 빈 트리의 기본 깊이 확인

추가 검증 2: 단일 노드

입력: root = [1]
기대 출력: 1
확인 결과: 통과
검증 목적: 노드 수 기준 깊이 계산 확인

추가 검증 3: 한쪽으로만 이어진 트리

입력: 1 -> 2 -> 3 -> 4
기대 출력: 4
확인 결과: 통과
검증 목적: 편향 트리에서 명시적 스택 순회 확인

6. 참고 풀이 비교

재귀 DFS는 점화식을 코드에 그대로 표현할 수 있어 짧고 읽기 쉽다. 이 글에서는 같은 DFS 상태를 스택에 (노드, 깊이)로 저장해 반복형으로 구현했다. 이렇게 하면 트리가 한쪽으로 길어져도 Python 재귀 호출 깊이에 의존하지 않는다.

마무리

Maximum Depth of Binary Tree는 트리의 각 서브트리 결과를 부모 노드에서 합치는 DFS의 기본 문제다. 빈 노드는 0, 현재 노드는 1로 세고 더 깊은 자식의 결과를 선택하면 최대 깊이를 구할 수 있다.

#트리#LeetCode#난이도 3