Ch.6 트리 기초

재귀로 트리 생각하기 — max depth, invert tree

트리 문제를 재귀적으로 분해하는 사고방식을 익힌다max depth와 invert tree를 재귀로 구현한다

트리 문제의 90%는 재귀로 풀린다

트리의 가장 강력한 특성은 서브트리도 트리라는 것입니다. 큰 문제를 작은 서브트리 문제로 나누면, 재귀가 나머지를 해결해줍니다.

재귀가 어렵게 느껴지는 이유 — 전체를 한번에 이해하려 하기 때문!

'왼쪽 서브트리와 오른쪽 서브트리가 이미 풀렸다면?' — 이 질문 하나로 대부분 해결됩니다.

lightbulb

핵심 개념

재귀(Recursion)

함수가 자기 자신을 호출하여 문제를 해결하는 방법

Base Case

재귀 호출을 멈추는 조건. 트리에서는 보통 None 노드

article

핵심 내용

트리의 마법: 서브트리도 트리다

재귀적 사고 3단계: 1. Base case: None이면 무엇을 반환? 2. 가정: 왼쪽/오른쪽 서브트리 답을 안다면? 3. 결합: 두 답을 어떻게 합치는가?

이 3단계를 외우세요. 면접에서 트리 문제를 만나면 자동으로 이 순서를 따릅니다

LeetCode #104. 트리의 최대 깊이를 구하라

재귀적 사고를 적용해봅시다. 1. Base: None이면 깊이 = 0 2. 가정: 왼쪽 깊이 L, 오른쪽 깊이 R을 안다 3. 결합: max(L, R) + 1

def maxDepth(root):
    # Base case
    if not root:
        return 0
    
    # 왼쪽/오른쪽 서브트리의 깊이
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    
    # 더 깊은 쪽 + 1 (현재 노드)
    return max(left_depth, right_depth) + 1

#       3
#      / \
#     9  20
#       /  \
#      15   7
# maxDepth = 3

코드가 단 4줄. 재귀적 사고가 왜 강력한지 느껴지나요?

시간 복잡도: O(n) — 모든 노드를 한 번씩 방문 공간 복잡도: O(h) — 재귀 깊이 = 트리 높이

maxDepth가 어떻게 동작하는지 단계별로 추적해봅시다

재귀는 리프에서 올라오며 답을 쌓습니다. 마치 나뭇잎에서 뿌리까지 물이 올라오듯이

LeetCode #226. 이진 트리를 좌우 반전하라

이 문제로 유명한 일화가 있습니다. Homebrew 개발자가 Google 면접에서 이 문제를 못 풀어 떨어졌다는...

재귀적 사고: 1. Base: None이면 None 반환 2. 가정: 왼/오 서브트리는 이미 뒤집어짐 3. 결합: 왼쪽 ↔ 오른쪽 교환

def invertTree(root):
    if not root:
        return None
    
    # 왼쪽·오른쪽을 재귀적으로 뒤집고
    left = invertTree(root.left)
    right = invertTree(root.right)
    
    # 교환!
    root.left = right
    root.right = left
    
    return root

# 입력:      출력:
#     4         4
#    / \       / \
#   2   7     7   2
#  / \ / \   / \ / \
# 1  3 6  9 9  6 3  1

핵심은 swap 한 줄. 재귀가 서브트리를 이미 처리했으므로 현재 노드에서는 교환만 하면 됩니다

시간 복잡도: O(n) — 모든 노드 방문 공간 복잡도: O(h) — 재귀 깊이 면접 포인트: 이 코드의 간결함 자체가 재귀의 힘을 보여줌

트리 재귀 문제는 크게 2가지 패턴으로 나뉩니다

패턴 1: 값 반환형 (bottom-up) • 리프에서 올라오며 값을 계산 • 예: maxDepth, 높이 구하기, 노드 수 세기 패턴 2: 구조 변경형 (top-down) • 루트에서 내려가며 구조를 변경 • 예: invertTree, flatten, prune

면접에서 트리 문제를 받으면 먼저 물어보세요: '이건 값을 구하는 건가, 구조를 바꾸는 건가?'

maxDepth에서 Base case로 None 노드에 대해 반환하는 값은?

invertTree의 시간 복잡도는?

트리 재귀의 공간 복잡도는 항상 O(n)이다

edit_note

정리 노트

재귀로 트리 생각하기

재귀적 사고 3단계

Base: None → 0 또는 None 반환
가정: 왼/오 서브트리 답을 이미 안다
결합: 두 답으로 현재 노드 답 계산

핵심 문제

maxDepth: max(L, R) + 1 → O(n)
invertTree: swap(left, right) → O(n)

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작