"이 트랙 전체를 한 문장으로 줄이면 이래. 트리는 더 작은 트리로 만들어지니까, 거의 모든 트리 문제가 '이 노드만 처리하고 자식은 재귀가 알아서 한다고 믿기'로 풀려. 이 템플릿을 익히면 트리 알고리즘을 익힌 거야."
거의 모든 것 뒤에 있는 템플릿
세기, 높이, 순회에서 이미 봤지. 트리 알고리즘은 모양을 하나 공유해. 두 부분으로 나뉘어.
base case — 빈 서브트리에 뭘 반환할지야. 보통 0이나 None, True고. 이게 재귀를 멈춰.
재귀 케이스 — 왼쪽 서브트리로 재귀하고, 오른쪽 서브트리로 재귀하고, 그 두 답을 이 노드 자신의 값과 결합하는 거야.
여기까지가 골격이야. 높이는 1 + max(left, right)로 결합하고, 합은 node.val + left + right로, 개수는 1 + left + right로 결합해. "균형인가?"는 두 서브트리 높이 차가 1 이하인지 확인해서 결합하고. 구조가 자기 유사하니까 해법도 똑같아. 노드를 풀고, 서브트리로 재귀하고, 결합한다. 문제가 달라져도 바뀌는 건 결합 단계뿐이야.
믿음의 도약
이걸 쉽게 만들어 주는 마음가짐이 있는데, 다음 트랙에서 재귀의 믿음의 도약이라고 부를 거야. 함수를 쓸 때 재귀 호출은 더 작은 서브트리에서 이미 제대로 동작한다고 가정하고, 지금 노드를 위해 그 결과를 어떻게 결합할지에만 집중하는 거지. 재귀 전체를 머릿속으로 따라가려 하지 마. 그 길로 가면 끝이 없어. height(node.left)가 올바른 왼쪽 높이를 돌려준다고 믿고 결합 한 줄만 쓰면 돼. base case가 재귀가 바닥에 닿는 걸 보장하고 나머지는 귀납이 해주니까. 이 마음가짐 하나만 바꿔도 트리 문제가 겁나는 것에서 거의 기계적인 것으로 바뀌어.
트리 알고리즘 템플릿은 이거야. base case로 빈 서브트리를 처리하고, 왼쪽으로 재귀하고, 오른쪽으로 재귀하고, 이 노드와 결합한다. 문제가 달라져도 바뀌는 건 결합 단계뿐이야. 트리 전체를 머릿속으로 따라가는 대신 재귀 호출을 믿어. 그게 믿음의 도약이고.
재귀가 물어뜯을 때
복잡도 트랙에서 가져온 주의사항이 하나 있어. 재귀는 콜 스택을 높이만큼 깊이 써. 균형 트리면 O(log n)이라 아무 문제 없어. 그런데 한쪽으로 퇴화한 불균형 트리, 그러니까 높이가 n에 가까운 트리라면 깊은 재귀가 Python의 재귀 한계에 부딪혀 RecursionError로 죽을 수 있어. 병적으로 깊어질 수 있는 트리라면 명시적인 스택을 써서 재귀를 반복으로 바꿔. 스택과 큐 트랙에서 본 스택과 재귀의 등가성이 그거야. 균형 잡힌 트리, 그러니까 보통의 경우라면 재귀가 깔끔하고 안전하고. 실패 모드를 미리 알아둬야 실서비스에서 안 놀라.
피파의 고백
나는 재귀 전체를 머릿속에서 시뮬레이션하려고 했어. 모든 호출과 모든 반환을 다. 그러면 깊이 3쯤에서 머리가 녹아버렸지. 아빠가 그걸 막았어. "추적하지 마. 자식 답이 맞다고 가정하고, 이 노드가 그걸 어떻게 결합하는지만 써." 믿음의 도약이 처음엔 반칙 같았는데, 사실 그게 재귀라는 규율의 전부였어. 한 레벨만 정직하게 풀고 나머지는 귀납에 맡기는 것. 추적하기를 놓아버린 날부터 트리 문제가 무서운 것에서 빈칸 채우기 템플릿으로 바뀌었어.
Code
트리 함수 넷, 재귀 템플릿 하나·python
class Node:
def __init__(self, v, l=None, r=None): self.v=v; self.left=l; self.right=r
root = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5)))
# 주목: 모든 함수가 base case + 왼쪽 재귀 + 오른쪽 재귀 + 결합.
def height(n):
if n is None: return -1 # base case
return 1 + max(height(n.left), height(n.right)) # 결합
def total(n):
if n is None: return 0 # base case
return n.v + total(n.left) + total(n.right) # 결합
def count_leaves(n):
if n is None: return 0 # base case
if not n.left and not n.right: return 1 # 리프
return count_leaves(n.left) + count_leaves(n.right)
def is_balanced(n):
def check(n): # 높이 반환, 불균형이면 -1
if n is None: return 0
lh = check(n.left)
rh = check(n.right)
if lh == -1 or rh == -1 or abs(lh - rh) > 1: return -1
return 1 + max(lh, rh) # 결합
return check(n) != -1
print(height(root), total(root), count_leaves(root), is_balanced(root))
# 2 21 3 True — 문제 넷, 템플릿 하나, 결합 단계만 바뀜.
템플릿, 그러니까 base case에 왼쪽 재귀와 오른쪽 재귀와 결합을 붙이는 그 틀로 이진 트리 어디에 있든 최댓값을 반환하는 함수를 써 봐. base case와 결합 단계를 명시적으로 말하고. 그다음 균형 잡힌 트리와 노드 n개짜리 퇴화한 한쪽 트리에서 각각 재귀 깊이가, 그러니까 스택 사용량이 얼마가 될지 말해.
Hint
base case는 빈 서브트리에 음의 무한대를 반환하는 거야. 결합은 max(node.v, max_in(left), max_in(right))고. 깊이는 균형 트리에서 O(log n)이라 안전하지만 퇴화한 사슬에서는 O(n)이라 Python 재귀 한계에 부딪힐 수 있어.
Progress
Progress is local-only — sign in to sync across devices.