현대의 소프트웨어 개발에서 알고리즘과 데이터 구조는 매우 중요한 부분을 차지합니다. 특히, 코딩테스트에서 자주 등장하는 문제 유형 중 하나가 트리 관련 문제입니다. 이 글에서는 리프 노드(Leaf Node)의 개수를 구하는 문제를 다룰 것입니다.
문제 정의
주어진 이진트리의 리프 노드의 개수를 구하는 문제입니다. 리프 노드는 자식이 없는 노드를 의미하며, 이진트리의 특성을 감안할 때, 리프 노드는 최대 2개의 자식을 가질 수 있습니다. 이 문제를 통해 재귀적 사고와 트리 탐색 알고리즘을 익히는 데 도움이 될 것입니다.
문제 설명
// 이진 트리 노드 정의
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
// 리프 노드의 개수를 구하는 메소드
int countLeafNodes(TreeNode root);
입력: 이진트리의 루트 노드(root).
출력: 리프 노드의 개수.
알고리즘 접근 방식
리프 노드를 찾기 위한 가장 일반적인 방법은 트리를 탐색하여 자식 노드가 없는 노드를 카운트하는 것입니다. 이 문제는 재귀적 접근을 통해 쉽게 해결할 수 있습니다.
재귀적 접근
재귀적으로 트리를 탐색하면서 각 노드에 대해 다음을 수행합니다:
- 현재 노드가 null이면, 0을 반환합니다.
- 현재 노드가 리프 노드인지 확인합니다. (왼쪽, 오른쪽 자식이 모두 null이라면)
- 리프 노드라면 1을 반환하고, 아니라면 왼쪽 서브트리와 오른쪽 서브트리에서 리프 노드의 개수를 각각 구하고 합칩니다.
구현
public class Main {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);
System.out.println("리프 노드의 개수: " + countLeafNodes(root));
}
public static int countLeafNodes(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
return countLeafNodes(root.left) + countLeafNodes(root.right);
}
}
예시
아래와 같이 이진 트리가 구성되어 있다고 가정해보겠습니다:
1
/ \
2 3
/ \ \
4 5 6
위 트리에서 리프 노드는 4, 5, 6이며, 따라서 리프 노드의 개수는 3입니다.
테스트 및 검증
구현한 메소드를 테스트하기 위해 여러 다양한 이진트리를 만들고 리프 노드의 개수를 검증합니다. 예를 들어, 노드가 1개인 트리, 왼쪽 / 오른쪽 편향 트리, 빈 트리 등을 만들어 테스트합니다.
테스트 케이스
// 단일 노드 트리
TreeNode singleNode = new TreeNode(1);
assert countLeafNodes(singleNode) == 1;
// 빈 트리
assert countLeafNodes(null) == 0;
// 왼쪽 편향 트리
TreeNode leftSkewedTree = new TreeNode(1);
leftSkewedTree.left = new TreeNode(2);
leftSkewedTree.left.left = new TreeNode(3);
assert countLeafNodes(leftSkewedTree) == 1;
// 오른쪽 편향 트리
TreeNode rightSkewedTree = new TreeNode(1);
rightSkewedTree.right = new TreeNode(2);
rightSkewedTree.right.right = new TreeNode(3);
assert countLeafNodes(rightSkewedTree) == 1;
복잡도 분석
시간 복잡도는 O(N)입니다. 모든 노드를 한번씩 방문해야 하므로, N은 노드의 수입니다. 공간 복잡도는 O(h)로, 여기서 h는 트리의 높이입니다. 최악의 경우(편향 트리) h는 N과 같을 수 있습니다.
결론
이 글에서 우리는 리프 노드의 개수를 구하는 알고리즘 문제를 다뤘습니다. 재귀적 사고를 통해 트리를 탐색하고, 기본적인 이진트리 개념을 이해하는 데 도움이 되었기를 바랍니다. 알고리즘 문제를 해결하는 과정에서, 항상 문제를 어떻게 나누고 해결할지를 고려해야 합니다. 다양한 트리 구조에 대해 연습해보는 것도 중요합니다.