6월 19일 발표날에 발표할 문제풀이 내용입니다.

전체 소스코드는 깃허브에 올려 두었습니다.

문제 선정 이유

• 루트 / 리프 노드, 트리의 재귀적 탐색, 트리의 높이 계산, 서브트리 구조 이해 등 기본 개념을 복습할 수 있는 문제라고 생각해 선택함

문제 분석

• 리프 노드: 자식이 없는 노드
• 서브트리: 트리의 특정 노드를 루트로 하여, 그 노드와 모든 자손으로 구성된 부분 트리

코드 풀이

• 재귀함수를 이용해 풀어야 함. 재귀함수 문제를 풀 때 중요한 점은
• 첫째, 함수를 잘 정의해야 한다
  • node를 루트로 하는 서브트리의 높이를 반환한다
• 둘째, 종료 조건을 잘 정의해야 한다
  • node = NULL인 경우, -1을 반환한다
  • 굳이 -1로 설정한 이유: 리프 노드가 루트인 트리의 높이를 0으로 처리하기 위해
    • height를 계산할 때 -1 + 1 = 0이 된다

int hasGreatGrandchild(BTNode *node)
{
    // node를 루트로 가진 서브트리의 높이를 반환
    // 높이가 3 이상이면, 이 노드는 증손주를 가짐

    // 종료조건 (NULL 노드의 높이는 -1로 정의)
	if (node == NULL) return -1;

    // 왼쪽, 오른쪽 서브트리의 높이를 재귀적으로 계산
    int left = hasGreatGrandchild(node -> left);
    int right = hasGreatGrandchild(node -> right);

    // 현재 트리의 높이 = 더 높은 서브트리 높이 + 1
    int height = left > right ? left + 1 : right + 1;

    // 현재 서브트리의 높이가 3 이상이면
    // 루트 노드는 증손주를 가짐
    if (height >= 3) {
        printf("%d ", node -> item);
    }

    // 현재 서브트리의 높이를 반환
    return height;
}

어려웠던 점

• 처음 문제를 봤을 때, 트리의 높이 개념이 잘 떠오르지 않아 문제풀이를 할 때 높이를 계산해야 한다는 점을 바로 떠올리지 못함