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

안녕하세요, 여러분! 오늘은 C#을 이용하여 알고리즘 문제를 해결하는 방법을 배워보겠습니다. 이번 주제는 이진 트리에서 리프 노드의 개수를 구하는 문제입니다. 이 문제를 풀면서 자료구조와 재귀 호출에 대한 이해도를 높일 수 있습니다.

1. 문제 정의

문제는 다음과 같습니다. 주어진 이진 트리가 있을 때, 리프 노드(자식 노드가 없는 노드)의 개수를 구하는 함수를 작성하시오.

예시

입력: 다음과 같은 이진 트리

출력: 3 (리프 노드: 4, 5, 3)

2. 이진 트리 소개

이진 트리는 각 노드가 최대 두 개의 자식을 가지는 트리 데이터 구조입니다. 이진 트리는 다음과 같은 특성을 가지고 있습니다:

각 노드는 자식 노드(왼쪽 및 오른쪽)를 가질 수 있습니다.
리프 노드는 자식 노드가 없는 노드를 의미합니다.
이진 트리는 재귀적 구조를 가집니다.

3. 접근 방법

리프 노드의 개수를 구하기 위해 재귀 함수를 사용하는 방법을 고려해보겠습니다. 기본적인 접근 방식은 다음과 같습니다:

현재 노드를 판단합니다. 만약 현재 노드가 null이라면, 0을 반환합니다.
현재 노드가 리프 노드(즉, 왼쪽 자식과 오른쪽 자식 모두 null)인 경우, 1을 반환합니다.
현재 노드가 리프 노드가 아니라면, 왼쪽과 오른쪽 서브트리에서 각각 리프 노드의 개수를 재귀적으로 구한 후 합산하여 반환합니다.

4. C# 코드 구현

이제 위에서 설명한 접근 방법에 따라 C#으로 코드를 구현해보겠습니다.

using System;

class TreeNode
{
    public int Val;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int val)
    {
        Val = val;
        Left = null;
        Right = null;
    }
}

class Program
{
    public static int CountLeafNodes(TreeNode root)
    {
        // 1. 현재 노드가 null인 경우
        if (root == null)
            return 0;

        // 2. 현재 노드가 리프 노드인 경우
        if (root.Left == null && root.Right == null)
            return 1;

        // 3. 왼쪽과 오른쪽 서브트리에서 리프 노드의 개수를 구함
        return CountLeafNodes(root.Left) + CountLeafNodes(root.Right);
    }

    static void Main(string[] args)
    {
        // 트리 생성
        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);
        Console.WriteLine($"리프 노드의 개수: {leafCount}");
    }
}

5. 코드 설명

코드에서 제공된 TreeNode 클래스는 이진 트리의 노드를 정의합니다. 각 노드는 값(Val)과 왼쪽 자식 노드(Left), 오른쪽 자식 노드(Right)를 가집니다. CountLeafNodes 함수는 주어진 노드에 대한 리프 노드의 개수를 재귀적으로 계산합니다.

첫 번째 조건문에서 현재 노드가 null인 경우 0을 반환하여 종료합니다.
두 번째 조건문에서 현재 노드가 리프 노드인 경우 1을 반환합니다.
마지막으로, 왼쪽과 오른쪽 서브트리를 각각 방문하여 결과를 합산하여 반환합니다.

6. 시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N)입니다. 여기서 N은 트리의 노드 개수를 나타냅니다. 각 노드를 한 번씩 방문하게 되므로, 선형 시간 복잡도를 가집니다.

7. 추가적인 고려사항

트리가 빈 경우, 즉 루트 노드가 null인 경우에는 리프 노드가 없습니다.
균형 이진 트리와 편향 이진 트리의 경우 모두 문제를 동일하게 처리할 수 있습니다.

8. 결론

이진 트리에서 리프 노드의 개수를 구하는 문제를 해결하는 방법을 배웠습니다. 재귀 함수를 사용하여 간단하게 해결할 수 있으며, 이 과정에서 트리 자료구조에 대한 이해도를 높일 수 있습니다.

다음 시간에는 다른 알고리즘 문제를 다루며 더 나아가겠습니다. 감사합니다!