이진 트리(binary tree)가 하나 주어졌을 때, 두 개의 숫자로 이루어진 결과를 반환하는 프로그램을 만들어 보겠습니다. 첫 번째 숫자는 트리에 포함된 잎(leaf) 노드의 개수이고, 두 번째 숫자는 잎이 아닌(non-leaf) 노드의 개수입니다.
문제 이해하기
예를 들어 다음과 같은 이진 트리가 입력으로 주어진다고 가정해 봅시다.
이 경우 출력은 (3, 2)가 됩니다. 잎 노드가 3개(값이 2, 10, 2인 노드)이고, 잎이 아닌 노드가 2개(값이 6, 6인 노드)이기 때문입니다.
풀이 접근 방식
이 문제는 재귀(recursion)를 활용하면 간단하게 해결할 수 있습니다. 알고리즘의 동작 순서는 다음과 같습니다.
- 현재 노드 n이 null이면 →
(0, 0)을 반환합니다. - n의 왼쪽 자식과 오른쪽 자식이 모두 null이면, 즉 n이 잎 노드라면 →
(1, 0)을 반환합니다. - 그렇지 않으면 왼쪽 서브트리와 오른쪽 서브트리에 대해 각각 재귀 호출을 수행합니다.
left := solve(n.left)
right := solve(n.right) - 마지막으로
(left[0] + right[0], 1 + left[1] + right[1])을 반환합니다. 여기서 첫 번째 값은 양쪽 서브트리의 잎 노드 수를 합한 것이고, 두 번째 값은 현재 노드 자신(1)을 더한 비-리프 노드 수입니다.
구현 예제
실제 파이썬 코드로 구현하면 다음과 같습니다.
class TreeNode:
def __init__(self, data, left=None, right=None):
self.val = data
self.left = left
self.right = right
class Solution:
def solve(self, n):
# 노드가 없으면 (잎 0개, 비-리프 0개)
if not n:
return 0, 0
# 왼쪽과 오른쪽 자식이 모두 없으면 잎 노드
if not n.left and not n.right:
return 1, 0
# 왼쪽, 오른쪽 서브트리를 재귀적으로 탐색
left, right = self.solve(n.left), self.solve(n.right)
return left[0] + right[0], 1 + left[1] + right[1]
ob = Solution()
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)
print(ob.solve(root))입력
root = TreeNode(6) root.left = TreeNode(2) root.right = TreeNode(6) root.right.left = TreeNode(10) root.right.right = TreeNode(2)
출력
(3, 2)
정리
이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(N)이며, 재귀 호출 깊이만큼 스택 공간을 사용하므로 공간 복잡도는 최악의 경우 O(N)(편향된 트리), 균형 잡힌 트리라면 O(log N)입니다. 재귀를 이용하면 잎 노드와 내부 노드의 개수를 깔끔하고 직관적으로 계산할 수 있습니다.