이진 트리는 컴퓨터 과학에서 중요한 데이터 구조 중 하나로,
모든 노드가 최대 두 개의 자식 노드를 가지는 트리입니다.
이진 트리는 탐색, 정렬, 데이터 저장 등의 여러 용도로 사용되며,
알고리즘 문제에서 자주 등장합니다.
이번 강좌에서는 이진 트리를 활용한 알고리즘 문제를 풀어보겠습니다.
문제: 이진 트리의 최대 깊이 구하기
이 문제는 주어진 이진 트리를 탐색하여 그 깊이를 계산하는 것입니다.
최대 깊이란 루트 노드부터 가장 깊은 잎 노드까지의 경로의 길이를 의미합니다.
이진 트리가 비어있다면 깊이는 0입니다.
다음은 입력 및 출력 형식입니다.
입력 형식
이진 트리는 배열 형태로 주어지며, 각 노드는 다음과 같이 정의됩니다:
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
출력 형식
이진 트리의 최대 깊이를 정수로 반환합니다.
예제
입력: [3,9,20,null,null,15,7]
출력: 3
문제 해결 접근법
이 문제를 해결하기 위해서는 이진 트리를 탐색하는 방법이 필요합니다.
우리는 주로 두 가지 방법으로 탐색할 수 있습니다:
깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS).
이 문제의 경우 DFS를 사용하여 재귀적으로 트리를 탐색하는 방법을 선택하겠습니다.
깊이 우선 탐색 – 재귀적 방법
재귀를 통해, 트리의 각 노드를 방문하면서
왼쪽과 오른쪽 자식 노드를 계속해서 호출하여 깊이를 확인합니다.
아래는 이 과정을 나타낸 알고리즘의 핵심 아이디어입니다.
- 현재 노드가 NULL이면 0을 반환합니다.
- 왼쪽 서브트리의 깊이를 재귀적으로 호출하여 얻습니다.
- 오른쪽 서브트리의 깊이를 재귀적으로 호출하여 얻습니다.
- 왼쪽과 오른쪽 깊이 중 더 큰 값을 선택하고, 1을 추가하여 반환합니다.
구현
이제 위에서 설명한 알고리즘을 C++ 코드로 구현해보겠습니다.
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
};
코드 설명
위 코드는 C++로 작성된 이진 트리 최대 깊이 계산하는 함수입니다.
maxDepth 함수가 재귀적으로 호출되어 주어진 노드의
최대 깊이를 계산합니다.
if (root == NULL)에서 노드가 NULL인지 체크합니다. NULL이면 깊이는 0이므로 반환합니다.- 왼쪽과 오른쪽 자식에 대해 각각의 깊이를 계산하고, 둘 중 더 큰 값을 선택하여 1을 더합니다.
- 최종적으로 반환되는 값은 전반적인 최대 깊이입니다.
테스트
이제 몇 가지 테스트 케이스를 통해 알고리즘의 기능을 확인해보겠습니다.
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
Solution solution;
int result = solution.maxDepth(root);
cout << result; // 3
결론
이진 트리의 최대 깊이를 계산하는 알고리즘을
C++로 구현하는 방법을 살펴보았습니다.
이 문제를 통해 재귀적인 탐색의 기초를 익힐 수 있었으며,
더 복잡한 트리 관련 문제를 해결하는 데 기초가 될 것입니다.
앞으로도 이진 트리에 대해 깊이 있는 공부를 해보시길 바랍니다.
감사합니다!