C++ 코딩테스트 강좌, 리프 노드의 개수 구하기

이 글에서는 C++ 프로그래밍 언어를 사용하여 리프 노드의 개수를 구하는 방법에 대해 자세히 설명하겠습니다. 알고리즘 문제를 해결하는 과정과 코드를 모두 포함하여 처음부터 끝까지 쉽게 이해할 수 있도록 구성하였습니다.

문제 설명

리프 노드는 자식 노드가 없는 노드를 의미합니다. 주어진 이진 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하십시오. 이 문제의 입력으로는 이진 트리의 루트 노드를 받을 것입니다.

입력 형식:

이진 트리의 루트 노드 (루트 노드는 nullptr일 수 있습니다.)

출력 형식:

리프 노드의 개수

알고리즘 접근 방식

이 문제를 해결하기 위해 우리는 재귀적으로 이진 트리를 탐색할 것입니다. 각 노드를 방문할 때마다 그 노드가 리프 노드인지 확인합니다. 리프 노드는 자식 노드가 없기 때문에, 왼쪽 및 오른쪽 자식 노드가 모두 nullptr인지 확인하면 됩니다.

구체적인 알고리즘:

루트 노드가 nullptr인 경우, 0을 반환합니다.
노드가 리프 노드일 경우, 1을 반환합니다.
왼쪽과 오른쪽 서브트리를 각각 재귀적으로 탐색하고, 그 결과를 합산하여 반환합니다.

C++ 코드 구현

이제 위의 알고리즘을 C++로 구현한 코드를 살펴보겠습니다.


#include <iostream>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int countLeafNodes(TreeNode* root) {
    // 1. 루트가 nullptr인 경우
    if (root == nullptr) {
        return 0;
    }
    
    // 2. 리프 노드인 경우
    if (root->left == nullptr && root->right == nullptr) {
        return 1;
    }
    
    // 3. 왼쪽과 오른쪽 서브트리 탐색
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

int main() {
    // 테스트용 이진 트리 생성
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    
    // 리프 노드의 개수 출력
    int leafCount = countLeafNodes(root);
    std::cout << "리프 노드의 개수: " << leafCount << std::endl;
    
    // 메모리 해제
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

코드 설명

위의 코드는 이진 트리의 루트 노드를 받아서 리프 노드의 개수를 반환하는 countLeafNodes 함수를 구현하였습니다.

구조체 선언:

TreeNode 구조체는 이진 트리의 각 노드를 표현합니다. 각 노드는 정수 값(val)과 왼쪽 자식(left) 및 오른쪽 자식(right) 포인터를 가지고 있습니다.

리프 노드 개수 세기:

countLeafNodes 함수는 먼저 루트가 nullptr인지 확인합니다. nullptr이면 0을 반환하고, 리프 노드인 경우 1을 반환합니다. 그렇지 않으면 왼쪽과 오른쪽 서브트리를 재귀적으로 호출하여 리프 노드 개수를 세어 합산합니다.

메인 함수:

메인 함수에서는 테스트용 이진 트리를 생성하고 그에 대한 리프 노드 개수를 출력합니다. 마지막으로 할당한 메모리를 해제하는 것도 잊지 말아야 합니다.

테스트 및 결과

이 코드를 실행하면 다음과 같은 결과를 얻게 됩니다:

리프 노드의 개수: 3

위의 이진 트리에서 리프 노드는 4와 5, 3 노드이므로 총 3개의 리프 노드가 존재합니다.

마무리

이 글에서는 C++로 이진 트리의 리프 노드 개수를 구하는 방법을 설명했습니다. 알고리즘을 이해하고 구현하는 과정의 예를 통해 C++의 기본적인 재귀 호출과 구조체 사용법을 배울 수 있습니다. 알고리즘 문제를 풀기 위해서는 문제를 쪼개고, 단계별로 접근하는 것이 중요합니다. 앞으로도 다양한 문제를 연습하여 알고리즘 실력을 쌓아가시기 바랍니다.