문제 개요
이진 트리(Binary Tree)가 주어졌을 때 다음 두 가지 작업을 수행해야 합니다.
- 각 레벨(level)에 리프 노드가 존재하면 해당 레벨에 있는 모든 리프 노드 값의 합을 구합니다. 리프 노드가 없는 레벨은 무시합니다.
- 구한 모든 합계를 서로 곱한 결과를 반환합니다.
예를 들어 아래와 같은 이진 트리가 입력으로 주어진다고 가정해 보겠습니다.
이 경우 출력값은 270입니다. 첫 번째와 두 번째 레벨에는 리프 노드가 없고, 세 번째 레벨에는 리프 노드 9 하나만 존재합니다. 마지막 레벨에는 2, 12, 5, 11 네 개의 리프 노드가 있습니다. 따라서 결과는 9 × (2 + 12 + 5 + 11) = 270이 됩니다.
접근 방법
이 문제는 큐(queue)를 이용한 BFS(너비 우선 탐색) 방식의 레벨 순회(level-order traversal)로 해결할 수 있습니다. 단계별 알고리즘은 다음과 같습니다.
- 루트가 null이면 0을 반환합니다.
- 결과를 저장할 변수 res를 1로 초기화합니다.
- 큐를 생성하고 루트 노드를 삽입합니다.
- 큐가 빌 때까지 다음 과정을 반복합니다.
- 현재 큐의 크기를 no_of_nodes에 저장하고, 크기가 0이면 반복을 종료합니다.
- sum_level은 0, found_leaf는 False로 초기화합니다.
- no_of_nodes가 0보다 큰 동안 큐에서 노드를 하나씩 꺼냅니다.
- 꺼낸 노드가 리프 노드라면 found_leaf를 True로 설정하고 노드 값을 sum_level에 더합니다.
- 현재 노드에 왼쪽 또는 오른쪽 자식이 있으면 큐의 끝에 추가합니다.
- 해당 레벨에서 리프 노드를 발견했다면 res에 sum_level을 곱합니다.
- 모든 레벨의 처리가 끝나면 res를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 실제 구현 방법을 확인해 보겠습니다.
class TreeNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
def isLeaf(root):
return (not root.left and not root.right)
def find_res(root):
if not root:
return 0
res = 1
que = []
que.append(root)
while True:
no_of_nodes = len(que)
if no_of_nodes == 0:
break
sum_level = 0
found_leaf = False
while no_of_nodes > 0:
curr_node = que[0]
if isLeaf(curr_node):
found_leaf = True
sum_level += curr_node.data
que.pop(0)
if curr_node.left != None:
que.append(curr_node.left)
if curr_node.right != None:
que.append(curr_node.right)
no_of_nodes -= 1
if found_leaf:
res *= sum_level
return res
root = TreeNode(8)
root.left = TreeNode(8)
root.right = TreeNode(6)
root.left.right = TreeNode(7)
root.left.left = TreeNode(9)
root.left.right.left = TreeNode(2)
root.left.right.right = TreeNode(12)
root.right.right = TreeNode(10)
root.right.right.left = TreeNode(5)
root.right.right.right = TreeNode(11)
print(find_res(root))
입력
root = TreeNode(8)
root.left = TreeNode(8)
root.right = TreeNode(6)
root.left.right = TreeNode(7)
root.left.left = TreeNode(9)
root.left.right.left = TreeNode(2)
root.left.right.right = TreeNode(12)
root.right.right = TreeNode(10)
root.right.right.left = TreeNode(5)
root.right.right.right = TreeNode(11)
출력
270
복잡도 분석
이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 큐에는 한 번에 최대 한 레벨의 노드만 저장되므로 공간 복잡도는 트리의 최대 폭 w에 비례하는 O(w)입니다.