1. 문제 설명
이 강좌에서는 스위프트를 활용하여 트리 구조에 대한 이해를 높이고, 이를 기반으로 한 알고리즘 문제를 해결합니다.
특히, 다음과 같은 문제를 다룰 것입니다:
문제: 이진 트리의 높이 구하기
주어진 이진 트리의 높이를 구하는 함수를 작성하시오. 이진 트리의 높이는 루트 노드에서 리프 노드까지의 최장 경로의 길이로 정의됩니다.
노드의 높이는 0부터 시작하며, 리프 노드는 높이가 0입니다.
2. 예시
아래와 같은 이진 트리가 주어질 때,
1
/ \
2 3
/ \
4 5
이 트리의 높이는 2입니다. 리프 노드인 4와 5가 루트 노드인 1로부터 두 단계 떨어져 있기 때문입니다.
3. 접근 방법
이 문제는 재귀적으로 해결할 수 있으며, 주요 아이디어는 다음과 같습니다:
- 재귀함수를 정의하여 현재 노드의 왼쪽과 오른쪽 자식 노드의 높이를 계산합니다.
- 각 자식 노드의 높이를 비교하여 최대값을 구합니다.
- 루트 노드의 높이는 1 + 왼쪽 자식 높이와 오른쪽 자식 높이 중 큰 값을 취합니다.
4. 구현하기
다음은 Swift로 구현한 이진 트리 높이 계산 함수입니다:
struct TreeNode {
var value: Int
var left: TreeNode?
var right: TreeNode?
}
func height(of node: TreeNode?) -> Int {
guard let node = node else {
return -1 // Null 노드는 -1 높이를 가집니다.
}
let leftHeight = height(of: node.left)
let rightHeight = height(of: node.right)
return max(leftHeight, rightHeight) + 1
}
5. 코드 설명
함수 height(of node: TreeNode?)는 재귀적으로 호출됩니다.
먼저, 노드가 nil(null)인 경우에는 -1을 반환하여 이는 리프 노드를 포함한 경로의 높이가 없음을 의미합니다.
왼쪽과 오른쪽 자식의 높이를 계산한 다음, 두 값 중 큰 것을 선택하고 1을 더하여 현재 노드의 높이를 반환합니다.
6. 시간 복잡도
이 알고리즘의 시간 복잡도는 O(N)입니다. 여기서 N은 트리의 노드 수를 나타냅니다.
모든 노드를 한 번씩 방문해야 하므로 시간이 비례하게 소요됩니다.
7. 추가 과제
사용자는 다음과 같은 추가 과제를 통해 더 많은 연습을 할 수 있습니다:
- 주어진 트리에서 특정 값이 존재하는지 확인하는 함수를 작성하시오.
- 이진 트리의 리프 노드를 모두 반환하는 함수를 작성하시오.
- 레벨 오더 트리 순회를 구현하여 모든 노드를 레벨 순서로 방문하시오.
8. 마무리
이번 강좌를 통해 이진 트리의 개념과 기본적인 높이 계산 알고리즘에 대해 알아보았습니다.
트리는 데이터 구조에서 매우 중요한 역할을 하며, 알고리즘 문제 해결에 있어 필수적으로 이해해야 하는 주제입니다.
트리 관련 문제는 코딩 테스트에서 자주 출제되므로 충분한 연습을 통해 실력을 향상시키세요.