"트랙 전체를 한 문장으로: 트리가 더 작은 트리로 만들어지니까, 거의 모든 트리 문제가 '이 노드 처리하고, 자식은 재귀가 처리한다고 믿어' 로 풀려. 그 템플릿을 익히면 트리 알고리즘을 익힌 거야."
거의 모든 것 뒤의 템플릿
세기, 높이, 순회에서 봤어: 트리 알고리즘은 모양 하나를 공유해. 두 부분이야:
base case — 빈 서브트리에 뭘 반환하나 (보통 0, None, True). 재귀를 멈춰.
재귀 케이스 — 왼쪽 서브트리 재귀, 오른쪽 서브트리 재귀, 그다음 그 답을 이 노드 자체 값이랑 결합.
그게 다야. 높이는 1 + max(left, right) 로 결합. 합은 node.val + left + right 로. 세기는 1 + left + right 로. "균형인가" 는 두 서브트리 높이가 ≤1 차이인지 확인으로 결합. 구조가 자기 유사라, 해법은: 노드 풀고, 서브트리 재귀하고, 결합. 다른 문제는 결합 단계만 바꿔.
믿음의 도약
이걸 쉽게 만드는 멘탈 트릭이 다음 트랙이 재귀의 믿음의 도약이라 부르는 거야: 함수 쓸 때, 재귀 호출이 더 작은 서브트리에서 이미 올바르게 작동한다고 가정하고, 현재 노드를 위해 그 결과를 결합하는 것만 신경 써. 전체 재귀를 머릿속에 추적하려 하지 마 — 그쪽엔 광기가 있어. height(node.left) 가 올바른 왼쪽 높이를 반환한다고 믿고, 결합 단계 하나만 써. base case 가 재귀가 바닥 치는 걸 보장하고, 귀납이 나머지를 해. 이 마음가짐 전환 하나가 트리 문제를 위협적인 데서 거의 기계적인 걸로 바꿔.
트리 알고리즘 템플릿: base case (빈 서브트리) 처리하고, 왼쪽 재귀, 오른쪽 재귀, 이 노드랑 결합. 다른 문제는 결합 단계만 바꿔. 전체 트리를 추적하는 대신 재귀 호출을 믿어 — 믿음의 도약.
재귀가 물어뜯을 때
Complexity 트랙에서 가져온 주의 하나: 재귀는 콜 스택을 써, O(높이) 깊이. 균형 트리면 O(log n) — 완전 괜찮아. 근데 퇴화한 불균형 트리 (높이 ≈ n) 면, 깊은 재귀가 Python 재귀 한계를 쳐 RecursionError 로 크래시할 수 있어. 병적으로 깊을 수 있는 트리엔, 명시적 스택으로 재귀를 반복으로 바꿔 (Stacks 트랙의 스택/재귀 동등성). 균형 트리엔 — 정상 케이스 — 재귀가 깔끔하고 안전해. 실패 모드를 알아둬서 production 에서 절대 안 놀라게.
피파의 고백
난 전체 재귀를 머릿속에 시뮬레이션하려 했어 — 모든 호출, 모든 반환 — 그러면 깊이 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.