트리의 재귀적 특성 활용하기

1. 트리가 재귀에 적합한 이유

트리는 "부모 + 자식(서브트리)" 구조로 되어 있다.
즉, 작은 문제(서브트리)를 해결 → 부모 노드에서 결과를 종합 → 전체 트리 해결

 

핵심 아이디어

자식 노드를 먼저 처리(재귀 호출) → 결과를 부모에서 합산 또는 가공

2. 대표 문제 유형

• 서브트리 크기 구하기
• 트리의 높이 구하기
• 부모 정보 기록
• 서브트리 값의 합 (Bottom-up)
• 값 전파 (Top-down)

3. 예시

(1) 서브트리 크기

int dfs(Node node) {
    int size = 1;
    for (Node child : node.children) {
        size += dfs(child);
    }
    return size;
}

(2) 트리 높이

int dfs(Node node) {
    if (node.children.isEmpty()) return 0;
    int maxDepth = 0;
    for (Node child : node.children) {
        maxDepth = Math.max(maxDepth, dfs(child));
    }
    return maxDepth + 1;
}

(3) 부모 정보 기록

void dfs(Node node, Node parent) {
    parentMap.put(node, parent);
    for (Node child : node.children) {
        dfs(child, node);
    }
}

(4) 서브트리 값의 합 (Bottom-up)

int dfs(Node node) {
    int sum = node.value;
    for (Node child : node.children) {
        sum += dfs(child);
    }
    return sum;
}

• 출제 포인트: "서브트리 합"이라는 키워드 → 자식 값을 모아서 부모가 계산

(5) 값 전파 (Top-down)

void dfs(Node node, int inheritedValue) {
    node.value += inheritedValue; // 부모로부터 받은 값 더함
    for (Node child : node.children) {
        dfs(child, node.value);   // 현재까지 누적된 값을 자식에게 전달
    }
}

• 출제 포인트: "부모에서 자식으로 정보 전달" → 전위 순회(Preorder) 형태

4. 출제 포인트

• "서브트리", "합산", "누적 값" 같은 단어가 보이면 DFS 재귀 패턴
• 자식 → 부모: 후위 순회(Postorder) / 부모 → 자식: 전위 순회(Preorder)
• DP + 트리 구조 → 거의 대부분 DFS 1회로 해결

 

[백준 11725] 트리의 부모 찾기 → 부모 정보 기록

[백준 15681] 트리와 쿼리 → 서브트리 크기 계산

[백준 2213] 트리의 독립집합 → 트리 DP (서브트리 값 합 패턴)

[LeetCode 124] Binary Tree Maximum Path Sum → 서브트리 값 합 응용

[백준 1991] 트리 순회 → 전위/중위/후위 순회 기본기