문제 설명
이진 트리에서 리프 노드는 자식 노드가 없는 노드를 말합니다. 주어진 이진 트리가 있을 때, 리프 노드의 개수를 구하는 함수를 작성하세요.
예를 들어:
- 입력:
1 / \ 2 3 / \ 4 5 - 출력: 3 (리프 노드: 4, 5, 3)
문제 분석
이 문제는 주어진 이진 트리에서 자식 노드가 없는 노드(즉, 리프 노드)의 개수를 셀 수 있는 알고리즘을 구현하는 것입니다. 재귀적인 방법이나 반복적인 방법을 통해 이진 트리를 순회하면서 리프 노드를 찾을 수 있습니다.
알고리즘 설계
리프 노드를 찾기 위해서는 다음과 같은 절차를 따릅니다:
- 이진 트리를 탐색하기 위한 함수를 정의합니다.
- 현재 노드가 NULL이 아닌 경우:
- 왼쪽 자식 노드를 재귀적으로 호출합니다.
- 오른쪽 자식 노드를 재귀적으로 호출합니다.
- 현재 노드가 리프 노드인지 확인합니다; 리프 노드일 경우 카운트를 증가시킵니다.
- NULL인 경우, 함수는 종료합니다.
스위프트 구현
이제 위의 알고리즘을 스위프트로 구현해보겠습니다. 아래는 리프 노드의 개수를 구하는 함수의 코드입니다:
class TreeNode {
var value: Int
var left: TreeNode?
var right: TreeNode?
init(value: Int) {
self.value = value
self.left = nil
self.right = nil
}
}
func countLeafNodes(root: TreeNode?) -> Int {
guard let node = root else {
return 0
}
// 리프 노드인지 확인
if node.left == nil && node.right == nil {
return 1
}
// 재귀적으로 왼쪽과 오른쪽 자식 노드의 리프 노드 개수를 센다
return countLeafNodes(root: node.left) + countLeafNodes(root: node.right)
}
코드 설명
위의 코드는 이진 트리의 리프 노드 개수를 구하기 위한 countLeafNodes 함수를 구현합니다. 각 부분을 분석하여 설명하겠습니다:
TreeNode클래스: 이진 트리의 각 노드를 정의합니다. 각 노드는 값과 왼쪽, 오른쪽 자식을 가집니다.countLeafNodes함수: 주어진 노드를 인자로 받아 리프 노드의 수를 반환합니다.guard let: 현재 노드가 NULL인지 확인하고, NULL일 경우 0을 반환하여 탐색을 종료합니다.- 리프 노드 확인: 현재 노드가 왼쪽과 오른쪽 자식 노드가 없으면 1을 반환합니다.
- 재귀 호출: 왼쪽과 오른쪽 자식 노드를 재귀적으로 호출하여 리프 노드의 개수를 더합니다.
테스트 케이스
작성한 함수가 올바르게 동작하는지 확인하기 위해 몇 가지 테스트 케이스를 만들어 보겠습니다.
// 트리 생성
let root = TreeNode(value: 1)
let node2 = TreeNode(value: 2)
let node3 = TreeNode(value: 3)
let node4 = TreeNode(value: 4)
let node5 = TreeNode(value: 5)
// 트리 구조 연결
root.left = node2
root.right = node3
node2.left = node4
node2.right = node5
// 리프 노드 개수 출력
let leafCount = countLeafNodes(root: root)
print("리프 노드의 개수: \(leafCount)") // 리프 노드의 개수: 3
결론
이번 글에서는 스위프트를 활용하여 이진 트리의 리프 노드 개수를 구하는 방법에 대해 알아보았습니다. 알고리즘을 설계하고, 이를 구현하는 과정에서 재귀 호출의 원리에 대해 이해하고 실제 코드를 작성하는 연습을 했습니다. 이와 같은 문제는 코딩 테스트에서 자주 출제되므로, 반복적으로 연습하여 숙련도를 높이는 것이 중요합니다.
추가 학습 자료
리프 노드 개수를 구하는 문제와 관련된 추가 자료를 찾고 싶다면, 다음 자료를 참고하시기 바랍니다: