[정글 코어타임] - [리트코드]104. Maximum Depth of Binary Tree

LeetCode · Tree · DFS · BFS · Easy

이진 트리에서 루트부터 가장 먼 리프까지의 깊이를 구하는 대표적인 트리 재귀 문제

문제 링크 바로가기

문제 한눈에 보기

문제 의미	이진 트리의 최대 깊이 = 루트에서 가장 먼 리프까지 가는 경로의 노드 개수
예시 출력	root = [3,9,20,null,null,15,7] 이면 정답은 3
대표 풀이	DFS(재귀)로 왼쪽 깊이와 오른쪽 깊이를 구한 뒤 더 큰 값에 1을 더한다
대체 풀이	BFS로 레벨을 하나씩 세면서 깊이를 구할 수도 있다

핵심 1

트리 문제는 자식의 결과를 먼저 구한 뒤 부모에서 계산하는 재귀 구조가 매우 자주 나온다.

핵심 2

현재 노드의 깊이는 1 + max(왼쪽 깊이, 오른쪽 깊이) 로 바로 표현할 수 있다.

핵심 3

노드가 없으면 깊이는 0 이라는 기저 조건이 재귀의 출발점이 된다.

최대 깊이란?

최대 깊이는 루트에서 시작해서 가장 아래쪽 리프 노드까지 내려가는 경로 중 가장 긴 경로의 노드 개수를 의미한다.

3 / \ 9 20 / \ 15 7

위 트리에서 가장 깊은 경로는 3 → 20 → 15 또는 3 → 20 → 7 이고, 노드 수는 3개이므로 최대 깊이는 3이다.

DFS 접근 핵심

트리는 보통 "현재 노드의 답 = 자식들의 답을 이용해 계산" 하는 형태로 접근하면 풀린다. 이 문제도 똑같다.

현재 노드 깊이 = 1 + max(왼쪽 서브트리 깊이, 오른쪽 서브트리 깊이)

즉, 왼쪽으로 내려간 결과와 오른쪽으로 내려간 결과 중 더 큰 값을 선택하고, 현재 노드 자신을 포함하기 위해 1을 더하면 된다.

최종 코드 (DFS 재귀)

class Solution(object):
    def maxDepth(self, root):
        if root is None:
            return 0

        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)

        return 1 + max(left, right)

한 줄씩 자세히 설명

줄	코드	설명
1	class Solution(object):	LeetCode에서 요구하는 클래스 형식이다.
2	def maxDepth(self, root):	현재 노드를 루트로 하는 트리의 최대 깊이를 반환하는 함수다.
3-4	if root is None: return 0	노드가 없다는 것은 더 내려갈 곳이 없다는 뜻이므로 깊이는 0이다. 이 부분이 재귀의 종료 조건이다.
6	left = self.maxDepth(root.left)	왼쪽 자식 서브트리의 최대 깊이를 재귀적으로 구한다.
7	right = self.maxDepth(root.right)	오른쪽 자식 서브트리의 최대 깊이를 재귀적으로 구한다.
9	return 1 + max(left, right)	왼쪽과 오른쪽 중 더 깊은 경로를 선택하고, 현재 노드 자신을 포함하기 위해 1을 더해 반환한다.

동작 흐름 시각화

예제 트리:

1 \ 2

maxDepth(1) → left = maxDepth(None) = 0 → right = maxDepth(2) → left = maxDepth(None) = 0 → right = maxDepth(None) = 0 → return 1 + max(0, 0) = 1 → return 1 + max(0, 1) = 2

핵심 감각은 끝까지 내려갔다가, 자식의 결과를 들고 부모에서 계산하며 올라오는 것이다.

왜 DFS가 더 자주 쓰일까?

이 문제는 BFS로도 풀 수 있지만, 최대 깊이 자체가 "아래 서브트리의 결과를 이용해 현재 답을 만든다"는 구조라서 DFS 재귀가 더 직관적이다.

방식	생각하는 흐름	특징
DFS	끝까지 내려갔다가 올라오며 계산	코드가 짧고 공식이 깔끔하다
BFS	레벨을 하나씩 세며 계산	층 개념이 눈에 잘 보인다

BFS 버전도 가능하다

from collections import deque

class Solution(object):
    def maxDepth(self, root):
        if not root:
            return 0

        queue = deque([root])
        depth = 0

        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            depth += 1

        return depth

BFS는 레벨 하나를 전부 처리할 때마다 depth += 1 을 하면 된다. 즉, 층 수 자체를 세는 방식이다.

자주 헷갈리는 포인트

헷갈리는 점	설명
깊이를 간선 수로 세야 하나, 노드 수로 세야 하나?	이 문제는 노드 개수 기준이다. 그래서 리프 노드 하나만 있어도 깊이는 1이다.
빈 트리의 깊이는 왜 0인가?	노드가 하나도 없기 때문이다. 이 값이 재귀 종료 조건의 기준이 된다.
왜 1 + left + right 가 아니고 1 + max(left, right) 인가?	우리는 전체 노드 수가 아니라 가장 긴 한 경로의 길이를 구하는 것이기 때문이다.
DFS와 BFS 중 무엇을 외워야 하나?	둘 다 가능하지만, 이 문제는 DFS 재귀 풀이를 먼저 익히는 것이 가장 좋다.

시간복잡도

각 노드를 한 번씩만 방문하므로 O(n)

공간복잡도

재귀 호출 스택 또는 큐에 의해 최악의 경우 O(n)

핵심 요약

• 최대 깊이는 루트에서 가장 먼 리프까지의 노드 개수다.
• DFS 재귀에서는 1 + max(left, right) 공식을 그대로 쓰면 된다.
• root is None → 0 이 기저 조건이다.
• 트리 문제는 보통 자식 결과를 받아 부모에서 계산한다는 감각이 매우 중요하다.

한 문장 정리

이 문제는 왼쪽 깊이와 오른쪽 깊이를 재귀로 구한 뒤 더 큰 값에 현재 노드 1을 더하면 끝나는, 트리 재귀의 가장 기본적인 형태다.

출처: LeetCode 104. Maximum Depth of Binary Tree