문제 개요
0부터 9 사이의 숫자만 포함하는 이진 트리가 있다고 가정해 보겠습니다. 이진 트리에서는 루트(root) 노드에서 리프(leaf) 노드까지 이어지는 모든 경로가 하나의 숫자를 나타낼 수 있습니다.
예를 들어 다음과 같은 트리가 있다고 합시다.
위 트리에는 21과 23이라는 두 개의 경로가 존재합니다. 따라서 최종 출력값은 21 + 23 = 44가 됩니다.
풀이 접근 방법
이 문제는 깊이 우선 탐색(DFS)을 활용한 재귀 함수로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
- dfs()라는 이름의 재귀 함수를 생성합니다. 이 함수는 현재 노드(root)와 누적 숫자(num)를 매개변수로 받으며, 처음 호출 시 num은 0으로 초기화됩니다.
- 현재 노드가 null이 아니라면 다음을 수행합니다.
- num := num * 10 + 현재 노드의 값
- 현재 노드가 리프 노드인지 확인합니다. 즉, 오른쪽 자식과 왼쪽 자식이 모두 null이라면:
- sum := sum + num
- num := num / 10
- 함수를 종료하고 반환합니다.
- dfs(오른쪽 자식 노드, num)를 호출합니다.
- dfs(왼쪽 자식 노드, num)를 호출합니다.
- num := num / 10
- 메서드를 종료하고 반환합니다.
- 초기 sum 값을 0으로 설정합니다.
- 루트 노드를 인자로 하여 dfs()를 호출합니다.
- 최종적으로 sum을 반환합니다.
Python 구현 예제
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def insert(temp, data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
class Solution(object):
def sumNumbers(self, root):
self.sum = 0
self.dfs(root)
return self.sum
def dfs(self, node, num=0):
if node:
num = num*10 + node.data
if not node.right and not node.left:
self.sum += num
num /= 10
return
self.dfs(node.right, num)
self.dfs(node.left, num)
num /= 10
return
ob1 = Solution()
tree = make_tree([2,1,3])
print(ob1.sumNumbers(tree))
입력
[2,1,3]
출력
44
동작 원리 정리
핵심 아이디어는 간단합니다. 트리를 따라 내려갈 때마다 기존 누적 값에 10을 곱한 뒤 현재 노드의 값을 더하면, 지나온 경로가 하나의 십진수 숫자처럼 이어집니다. 그리고 리프 노드에 도달했을 때 그 경로 숫자를 전체 합계에 더해주면 됩니다. 이 방식의 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(n)이며, 공간 복잡도는 재귀 호출 스택의 깊이에 비례하여 최악의 경우 O(n)입니다.