← 전체 회차
A-047● Day 472026.06.22easyleetcode #104neetcode150

이진 트리의 최대 깊이

#tree#depth-first-search#breadth-first-search#binary-tree
↗ leetcode #104 · maximum-depth-of-binary-tree
01

문제

· problem
P.047

이진 트리의 최대 깊이

↗ leetcode #104

이진 트리의 루트가 주어졌을 때, 그것의 최대 깊이를 반환하세요. 이진 트리의 최대 깊이는 루트 노드에서 가장 먼 리프 노드까지 가는 가장 긴 경로 위의 노드 개수입니다.

제약
  • · 0 ≤ number of nodes ≤ 10^4
  • · -100 ≤ Node.val ≤ 100
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[3,9,20,null,null,15,7]
3
example 2input → output
[1,null,2]
2
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    빈 트리(root = null)의 최대 깊이는 0입니까?
  • ☐
    최대 깊이는 가장 긴 경로의 노드 개수입니까 아니면 엣지 개수입니까?
  • ☐
    루트 노드만 있는 트리의 깊이는 몇입니까?
  • ☐
    null 자식 노드는 깊이 계산에 포함되어야 합니까?
  • ☐
    최대 깊이를 찾기 위해 모든 노드를 반드시 방문해야 합니까?
  • ☐
    스택을 명시적으로 사용하여 재귀 없이 구현할 수 있습니까?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 기본 케이스: 빈 트리 확인
○
if not root:
○
if root.left is None and root.right is None:
○
if root is not None:
step 2· 기본 케이스: 반환값│ 중첩
○
return 0
○
return 1
○
return -1
step 3· 재귀: 왼쪽 서브트리 탐색
○
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
○
self.maxDepth(root.left.left)
○
self.maxDepth(root.right)
step 4· 결과 결합: 더 깊은 쪽 선택
○
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
○
left_depth + right_depth
○
max(left_depth, right_depth)
step 5· 완전 반환문: 현재 노드 포함
○
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
○
return 1 + self.maxDepth(root.left) + self.maxDepth(root.right)
○
return max(self.maxDepth(root.left), self.maxDepth(root.right))
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
# RECURSIVE DFS
2
class Solution:
3
    def maxDepth(self, root: TreeNode) -> int:
4
        if not root:
5
            return 0
6
7
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
8
9
10
# ITERATIVE DFS
11
class Solution:
12
    def maxDepth(self, root: TreeNode) -> int:
13
        stack = [[root, 1]]
14
        res = 0
15
16
        while stack:
17
            node, depth = stack.pop()
18
19
            if node:
20
                res = max(res, depth)
21
                stack.append([node.left, depth + 1])
22
                stack.append([node.right, depth + 1])
23
        return res
24
25
26
# BFS
27
class Solution:
28
    def maxDepth(self, root: TreeNode) -> int:
29
        q = deque()
30
        if root:
31
            q.append(root)
32
33
        level = 0
34
35
        while q:
36
37
            for i in range(len(q)):
38
                node = q.popleft()
39
                if node.left:
40
                    q.append(node.left)
41
                if node.right:
42
                    q.append(node.right)
43
            level += 1
44
        return level
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[3,9,20,null,null,15,7]
→
3
case 2
[1,null,2]
→
2
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.