1. 문제 설명
삽입과 삭제가 자주 일어나는 데이터 구조로 트리가 널리 사용되고 있습니다.
이번 글에서는 이진 트리의 기본 개념과 활용 방법을 설명하고, 관련된 알고리즘 문제를 함께 풀어보겠습니다.
문제: 이진 트리의 최대 깊이 구하기
주어진 이진 트리의 루트 노드가 주어졌을 때, 트리의 최대 깊이를 구하는 함수를 작성하세요.
문제 요구 사항
- 트리의 각 노드는 정수 값을 가지며, 왼쪽과 오른쪽 자식을 가질 수 있습니다.
- 리프 노드는 자식이 없는 노드를 의미합니다.
- 트리의 최대 깊이는 루트 노드부터 리프 노드까지의 길이를 의미합니다.
2. 예시
입력: 3
/ \
9 20
/ \
15 7
출력: 3
설명: 이진 트리의 최대 깊이는 3입니다 (루트 노드 3 -> 노드 20 -> 노드 15 또는 7).
3. 트리 구조 이해하기
이진 트리는 각 노드가 최대 두 개의 자식을 가질 수 있는 트리입니다.
이진 트리는 다양한 방법으로 표현할 수 있지만, 노드를 클래스나 구조체로 구현하는 것이 일반적입니다.
아래는 이진 트리를 C#으로 구현한 예제입니다:
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
val = x;
left = null;
right = null;
}
}
4. 최대 깊이 구하기 알고리즘
최대 깊이를 구하는 방법은 재귀를 사용하여 구현할 수 있습니다.
각 노드에 대해 다음과 같은 절차를 따릅니다:
- 현재 노드가 null인 경우, 깊이는 0입니다.
- 현재 노드의 왼쪽 자식과 오른쪽 자식에 대해 재귀적으로 깊이를 구합니다.
- 왼쪽과 오른쪽 자식 깊이 중 큰 값에 1을 더하여 현재 노드의 깊이를 반환합니다.
5. C# 코드 구현
public int MaxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = MaxDepth(root.left);
int rightDepth = MaxDepth(root.right);
return Math.Max(leftDepth, rightDepth) + 1;
}
6. 전체 코드
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
val = x;
left = null;
right = null;
}
}
public class Solution {
public int MaxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = MaxDepth(root.left);
int rightDepth = MaxDepth(root.right);
return Math.Max(leftDepth, rightDepth) + 1;
}
}
7. 코드 분석
위의 코드에서 주목해야 할 점은:
- 재귀 호출을 통해 트리를 순회하고, 각 노드의 깊이를 구합니다.
- Math.Max 함수를 사용하여 두 가지 깊이의 최대값을 계산합니다.
- 기본 케이스(루트가 null인 경우)를 적절히 처리하여 무한 루프를 방지합니다.
8. 시간 복잡도
이 알고리즘의 시간 복잡도는 O(N)입니다.
여기서 N은 노드의 수입니다. 모든 노드를 한 번씩 방문해야 하기 때문입니다.
9. 추가 사항: 트리 순회 방법
트리를 다룰 때 여러 가지 순회 방식이 있습니다. 대표적으로:
- 전위 순회 (Pre-order): 현재 노드 → 왼쪽 자식 → 오른쪽 자식
- 중위 순회 (In-order): 왼쪽 자식 → 현재 노드 → 오른쪽 자식
- 후위 순회 (Post-order): 왼쪽 자식 → 오른쪽 자식 → 현재 노드
각 순회 방법을 이용해 특정 문제를 해결하기도 합니다. 이에 대한 내용은 이후 블로그 포스트에서 다룰 것입니다.
10. 마무리
이번 포스트에서는 이진 트리의 최대 깊이를 구하는 문제를 다뤘습니다.
트리 구조는 다양한 문제를 해결할 수 있는 강력한 도구이므로, 이론을 잘 이해하고 관련 문제를 자주 풀어보는 것이 중요합니다.
다음 시간에는 트리 관련 다른 문제들과 그 솔루션들에 대해 알아보겠습니다.