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

안녕하세요, 여러분! 이번 강좌에서는 코틀린을 통해 리프 노드의 개수를 구하는 알고리즘 문제를 다룰 것입니다. 리프 노드는 이진 트리에서 자식이 없는 노드를 의미하며, 이러한 데이터를 효율적으로 처리하는 방법에 대해 알아보겠습니다.

문제 설명

이진 트리가 주어질 때, 리프 노드의 개수를 구하는 함수를 작성하세요. 리프 노드는 자식이 없는 노드로 정의됩니다. 이 문제를 해결하기 위해 아래의 클래스 구조를 사용합니다:

class TreeNode(val value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

입력 예시

트리 구조

출력 예시

리프 노드 개수: 3

문제 해결 접근 방법

이 문제를 해결하기 위해 우리는 재귀적인 방법을 사용할 것입니다. 트리를 탐색하며 각 노드가 리프 노드인지 확인하고, 리프 노드일 경우 개수를 카운트합니다. 구체적인 절차는 다음과 같습니다:

기본 케이스로, 현재 노드가 null이라면 0을 반환합니다.
현재 노드가 리프 노드(즉, 왼쪽 자식과 오른쪽 자식이 모두 null인 경우)라면 1을 반환합니다.
그렇지 않다면, 왼쪽과 오른쪽 서브트리를 재귀적으로 탐색하여 리프 노드 개수를 더합니다.

코드 구현

위의 접근 방법을 기반으로 코드를 구현해보겠습니다:

fun countLeafNodes(root: TreeNode?): Int {
    // 기본 케이스: 현재 노드가 null인 경우
    if (root == null) {
        return 0
    }
    
    // 리프 노드인 경우
    if (root.left == null && root.right == null) {
        return 1
    }
    
    // 왼쪽과 오른쪽 서브트리의 리프 노드 개수를 재귀적으로 계산
    return countLeafNodes(root.left) + countLeafNodes(root.right)
}

테스트 케이스

함수가 제대로 작동하는지 확인하기 위해 여러 테스트 케이스를 작성해 보겠습니다:

fun main() {
    // 예제 트리 생성
    val root = TreeNode(1).apply {
        left = TreeNode(2).apply {
            left = TreeNode(4)
            right = TreeNode(5)
        }
        right = TreeNode(3)
    }
    
    // 리프 노드 개수 계산
    val leafCount = countLeafNodes(root)
    println("리프 노드의 개수: $leafCount") // 예상 출력: 3
}

복잡도 분석

이 문제의 시간 복잡도는 O(n)입니다. 모든 노드를 한 번씩 방문하기 때문입니다. 공간 복잡도는 O(h)로, h는 트리의 높이입니다. 이는 함수 호출 스택에 의해 결정됩니다.

마무리

이번 강좌에서는 코틀린을 이용하여 이진 트리에서 리프 노드를 세는 문제를 해결해 보았습니다. 알고리즘 문제 해결 과정에서 재귀의 중요성과 자료 구조에 대한 이해도를 높일 수 있었습니다. 추가적인 문제를 통해 더 많은 것을 배워나가길 바랍니다!

감사합니다. 다음 강좌에서 또 만나요!