이진 트리 Q2. 트리의 높이 구하기

자료구조 C 실습 · 이진 트리 · Q2

이진 트리 Q2. 트리의 높이 구하기

C 파일 하나를 문제 하나로 보고 정리한 풀이 글이다.
이번 글은 함수가 실제로 어떤 연결, 순회, 변환을 수행하는지에 초점을 맞춘다.

Section E Binary Tree maxHeight

루트에서 가장 깊은 리프까지의 높이를 구하는 고전적인 재귀 문제다. 현재 노드의 높이는 `max(왼쪽 높이, 오른쪽 높이) + 1`로 계산된다. 이 패턴은 트리 DP의 기본형이다.

한눈에 보는 문제 정보

원본 파일: C:\Users\cedis\OneDrive\문서\ANTIWORK\WEKK6~~~~~\data_structures_docker\Data-Structures\Binary_Tree\Q2_E_BT.c

대상 함수: maxHeight

카테고리: 이진 트리

문제에서 요구한 것

메뉴와 출력 문자열을 보면 이 파일은 특정 자료구조 연산 하나를 직접 구현하도록 만든 실습 문제다. 입력 흐름은 아래처럼 정리할 수 있다.

• 1: Create a binary tree.
• 2: Find the maximum height of the binary tree.
• 0: Quit
• The resulting binary tree is
• The maximum height of the binary tree is: %d
• Input an integer that you want to add to the binary tree. Any Alpha value will be treated as NULL.

핵심 구현 흐름

STEP 1

빈 노드는 높이 0으로 처리한다.

STEP 2

왼쪽과 오른쪽 서브트리의 높이를 각각 재귀 호출로 구한다.

STEP 3

둘 중 큰 값에 1을 더해 현재 노드 높이를 반환한다.

핵심 코드

문제 파일 전체를 다 옮기기보다, 실제로 구현해야 했던 함수만 뽑아서 보면 로직이 더 선명하게 들어온다.

핵심 코드: maxHeight

int maxHeight(BTNode *node)
{

    if (node == NULL)
    {
        return -1;
    }

    int leftHeight = maxHeight(node->left);
    int rightHeight = maxHeight(node->right);

    if(node->left == NULL && node->right == NULL)
    {
        return 0;
    }
    else
    {
        if (leftHeight > rightHeight)
        {
            return leftHeight + 1;
        }
        else
        {
            return rightHeight + 1;
        }
    }
}

구현할 때 체크할 점

• 노드 수와 높이를 혼동하면 기준값이 어긋난다.
• 빈 트리의 높이를 0으로 둘지 -1로 둘지 문제 정의를 먼저 맞춰야 한다.

마무리

이 문제는 거대한 알고리즘을 묻는 문제라기보다, 자료구조를 실제 포인터 연결과 순회 흐름으로 이해하고 있는지 확인하는 실습에 가깝다. 현재 노드의 높이는 `max(왼쪽 높이, 오른쪽 높이) + 1`로 계산된다. 이 패턴은 트리 DP의 기본형이다.

같은 카테고리의 다른 문제와 함께 보면, 연결 리스트에서는 재배선, 스택과 큐에서는 순서 제어, 트리에서는 재귀 순회라는 감각이 반복해서 나온다는 점도 같이 볼 수 있다.