각 노드에 0부터 9 사이의 한 자릿수가 저장되어 있는 이진 트리가 있다고 가정해 보겠습니다. 루트(root)에서 리프(leaf)까지 이어지는 각 경로는 노드의 값을 순서대로 이어 붙여 하나의 숫자를 만들어냅니다. 이때 우리가 구해야 하는 것은 트리 안의 모든 경로가 나타내는 숫자들의 총합입니다.
예를 들어 입력 트리가 다음과 같다면,
출력은 913이 됩니다. 루트에서 리프까지의 경로는 세 가지가 있으며, 각 경로가 만드는 숫자는 다음과 같습니다.
- 4 → 6 = 46
- 4 → 3 → 2 = 432
- 4 → 3 → 5 = 435
따라서 전체 합은 46 + 432 + 435 = 913입니다.
문제 해결 접근 방법
이 문제는 깊이 우선 탐색(DFS)과 재귀를 활용하면 간단하게 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- solve() 함수 정의: 매개변수로 현재 노드(root)와 지금까지 지나온 노드 값을 이어 붙인 문자열(string, 기본값은 빈 문자열)을 받습니다.
- 리프 노드 처리: 현재 노드가 존재하고 왼쪽·오른쪽 자식이 모두 없다면, 누적된 문자열에 현재 노드의 값을 덧붙인 뒤 정수로 변환하여 반환합니다. 이것이 하나의 완성된 경로 숫자입니다.
- total 초기화: 경로 숫자들의 합을 저장할 변수 total을 0으로 설정합니다.
- 왼쪽 서브트리 탐색: 왼쪽 자식이 존재하면, solve(왼쪽 자식, string + 현재 노드 값)의 반환값을 total에 더합니다.
- 오른쪽 서브트리 탐색: 오른쪽 자식이 존재하면, solve(오른쪽 자식, string + 현재 노드 값)의 반환값을 total에 더합니다.
- 결과 반환: 최종적으로 total을 반환합니다.
구현 예제
아래 파이썬 코드를 통해 실제 동작을 확인해 보겠습니다.
class TreeNode:
def __init__(self, data, left=None, right=None):
self.val = data
self.left = left
self.right = right
class Solution:
def solve(self, root, string=""):
if root and not root.left and not root.right:
return int(string + str(root.val))
total = 0
if root.left:
total += int(self.solve(root.left, string + str(root.val)))
if root.right:
total += int(self.solve(root.right, string + str(root.val)))
return total
ob = Solution()
root = TreeNode(4)
root.left = TreeNode(6)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(5)
print(ob.solve(root))입력
root = TreeNode(4) root.left = TreeNode(6) root.right = TreeNode(3) root.right.left = TreeNode(2) root.right.right = TreeNode(5)
출력
913
동작 원리 정리
이 알고리즘은 루트에서 출발해 각 노드를 지날 때마다 해당 노드의 값을 문자열 뒤에 이어 붙입니다. 리프 노드에 도달하는 순간, 그동안 쌓인 문자열이 곧 하나의 경로가 나타내는 숫자가 되므로 이를 정수로 변환해 반환합니다. 재귀 호출이 모두 끝나면 각 경로의 숫자들이 합산되어 최종 결과가 도출됩니다.
시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(N)(N은 노드 수)이며, 공간 복잡도는 재귀 호출 스택의 깊이에 비례하여 최악의 경우 O(H)(H는 트리의 높이)입니다.