1. 문제 정의
이 문제는 이진 트리(binary tree)에서 리프 노드의 개수를 구하는 것입니다. 리프 노드는 자식 노드가 없는 노드를 의미합니다. 자식 노드가 없는 노드의 개수를 세는 것은 트리의 구조를 이해하고 탐색 알고리즘을 활용하는 좋은 연습입니다. 이 문제를 해결하기 위해 재귀(Recursive) 또는 비재귀(Iterative) 방식으로 접근할 수 있습니다.
2. 문제 예시
다음과 같은 이진 트리가 주어졌다고 가정해보겠습니다:
1
/ \
2 3
/ \
4 5
위 트리의 리프 노드는 4와 5, 3 총 3개입니다. 이와 같은 트리를 입력으로 받아 리프 노드의 개수를 반환해야 합니다.
3. 알고리즘 접근 방식
리프 노드의 개수를 구하는 방법은 여러 가지가 있습니다. 우리가 사용할 가장 일반적인 방법은 재귀를 이용한 DFS(Depth-First Search)입니다. 이 방법은 트리를 깊이 우선으로 탐색하면서 리프 노드를 찾고, 이를 카운트하는 방식입니다.
4. 알고리즘 설명
다음은 리프 노드의 개수 구하는 알고리즘의 기본 구상입니다:
- 입력으로 주어진 노드가 null인지 확인한다. null이라면, 0을 반환한다.
- 노드가 리프 노드라면(즉, 왼쪽과 오른쪽 자식이 모두 null이라면) 1을 반환한다.
- 왼쪽 서브트리와 오른쪽 서브트리를 재귀적으로 호출하여 각각의 리프 노드 개수를 구한다.
- 왼쪽과 오른쪽 리프 노드의 개수를 합산하여 반환한다.
5. 자바스크립트 구현
다음은 위의 알고리즘을 자바스크립트를 사용해 구현한 코드입니다:
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function countLeafNodes(node) {
// 베이스 케이스: null 노드
if (node === null) {
return 0;
}
// 리프 노드 조건
if (node.left === null && node.right === null) {
return 1;
}
// 재귀 호출로 리프 노드 개수 세기
return countLeafNodes(node.left) + countLeafNodes(node.right);
}
// 예시 트리 구성
const 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);
console.log(countLeafNodes(root)); // Expected output: 3
6. 알고리즘 분석
이 알고리즘의 시간 복잡도는 O(n)입니다. 트리의 모든 노드를 한 번씩 방문해야 하기 때문입니다. 여기서 n은 노드의 수를 의미합니다. 공간 복잡도는 최악의 경우 O(h)로, h는 트리의 높이를 의미합니다. 이는 재귀 호출 스택의 깊이에 따른 것입니다.
만약 트리가 비어있거나 모든 노드가 한 쪽으로 치우쳐 있다면, 스택 깊이가 증가할 수 있습니다. 트리가 균형잡혀 있다면, 높이는 log(n)이 됩니다.
7. 비재귀적 방법
비재귀적 방법으로 DFS를 구현할 수도 있습니다. 스택을 사용하여 현재 노드를 추적하고, 자식 노드가 없는 노드를 카운트하는 방식입니다. 아래는 비재귀적 구현의 예시입니다:
function countLeafNodesIterative(root) {
if (root === null) {
return 0;
}
let stack = [root];
let leafCount = 0;
while (stack.length > 0) {
let node = stack.pop();
// 노드가 리프 노드인지 확인
if (node.left === null && node.right === null) {
leafCount++;
}
// 자식 노드를 스택에 추가
if (node.right !== null) {
stack.push(node.right);
}
if (node.left !== null) {
stack.push(node.left);
}
}
return leafCount;
}
console.log(countLeafNodesIterative(root)); // Expected output: 3
8. 결론
이 강좌에서는 이진 트리에서 리프 노드를 구하는 방법에 대해 살펴보았습니다. 재귀적 및 비재귀적 방법을 모두 사용하여 접근할 수 있음을 확인했습니다. 이 문제를 해결함으로써 트리 데이터 구조와 DFS 탐색 알고리즘을 보다 깊이 이해하는 데 도움이 되었기를 바랍니다. 알고리즘의 성능 분석을 통해 효율성을 고려하며 문제를 풀어보는 것이 데이터 구조와 알고리즘 학습에 중요하다는 점을 강조하고 싶습니다.