파이썬 코딩테스트 강좌, 리프 노드의 개수 구하기

문제 설명

주어진 이진 트리를 탐색하여 리프 노드의 개수를 계산하는 함수를 작성하세요. 리프 노드는 자식 노드가 없는 노드를 의미합니다.

입력

• 트리의 루트를 나타내는 노드 객체, Node 클래스가 주어집니다.

출력

• 리프 노드의 개수를 나타내는 정수 값

제한 사항

• 트리는 최대 10⁴개의 노드를 가질 수 있습니다.

이진 트리의 생성 및 구조

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 자료 구조입니다. 기본적으로 이진 트리는 루트 노드에서 시작하여 자식 노드로 구성됩니다. 아래는 이진 트리의 노드 클래스를 정의하는 방법입니다.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

위의 코드에서, Node 클래스는 각 노드의 값을 저장하고 왼쪽 및 오른쪽 자식 노드를 가리키는 포인터를 포함합니다. 이제 이 노드 구조를 사용하여 이진 트리를 생성할 수 있습니다.

리프 노드 개수 세기

리프 노드는 자식 노드가 없는 노드를 의미하며, 이를 세기 위해서는 트리를 탐색해야 합니다. 일반적으로 이진 트리를 탐색하는 방법으로는 전위, 중위, 후위 순회가 있습니다. 여기서는 후위 순회를 사용하여 리프 노드를 세는 방법을 살펴보겠습니다.

후위 순회 알고리즘

후위 순회는 다음의 과정을 통해 이루어집니다:

1. 왼쪽 서브트리를 후위 순회합니다.
2. 오른쪽 서브트리를 후위 순회합니다.
3. 현재 노드를 방문합니다.

이 과정을 이용하여 부모 노드가 리프 노드인지 확인할 수 있습니다. 리프 노드인 경우 카운터를 증가시키는 방식으로 리프 노드의 개수를 셉니다.

코드 구현

def count_leaf_nodes(root):
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return 1
    return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)

위의 count_leaf_nodes 함수는 재귀적으로 이진 트리를 탐색하여 리프 노드 수를 계산합니다.

문제 해결 과정 상세 설명

해당 문제를 해결하는 과정을 단계별로 살펴보겠습니다.

1단계: 기본적인 트리 생성

이진 트리를 생성하기 위해 몇 개의 노드를 정의해야 합니다. 예를 들어, 다음과 같은 트리를 생각해보겠습니다.

# 이진 트리 생성
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)

위 코드는 다음과 같은 이진 트리를 구성합니다:

2단계: 기본 함수 테스트

이제 우리가 작성한 count_leaf_nodes 함수를 사용하여 리프 노드의 개수를 계산할 수 있습니다.

leaf_count = count_leaf_nodes(root)
print(f"리프 노드의 개수: {leaf_count}")

위 코드를 실행하면 이진 트리에 존재하는 리프 노드의 개수를 출력합니다. 여기서는 리프 노드가 3개(4, 5, 6)이므로 출력 결과는 “리프 노드의 개수: 3″이 됩니다.

시간 복잡도 분석

위 알고리즘의 시간 복잡도는 O(n)입니다. 이는 트리에 존재하는 모든 노드를 방문해야 하기 때문입니다. n은 노드의 개수를 나타냅니다.

결론

오늘의 강좌에서는 이진 트리에서 리프 노드의 개수를 계산하는 문제를 다뤘습니다. 이 과정에서 재귀적인 접근 방식과 후위 순회의 개념을 적용했습니다. 이 문제는 코딩 테스트와 실제 개발에서도 자주 등장하는 문제이므로 꼭 이해하고 넘어가시기 바랍니다.

다음 강좌에서는 이진 트리를 더욱 깊이 있게 탐구하고, 다양한 트리 문제를 다뤄보도록 하겠습니다. 감사합니다.