2024년부터 새롭게 다시 시작하는 코딩테스트
2024년 4월 15일 (월)
Leetcode daily problem
129. Sum Root to Leaf Numbers
https://leetcode.com/problems/sum-root-to-leaf-numbers/?envType=daily-question&envId=2024-04-15
Problem
0부터 9까지의 숫자를 포함하는 이진 트리가 주어진다.
트리의 각 root-leaf의 경로는 숫자를 나타내는데,
예를 들어 root-leaf 경로 1 -> 2 -> 3은 숫자 123을 나타낸다.
모든 root에서 leaf까지의 숫자의 총합을 반환한다.
답변이 32비트 정수에 맞도록 테스트 케이스가 생성된다.
leaf 노드는 자식이 없는 노드, 터미널 노드를 의미한다.
Solution
DFS(Depth-frist search) 탐색
주어진 이진트리의 루트부터 터미널 노드까지의 경로까지 각 노드들의 숫자의 합을 더하는데 단순히 합을 구하는 것이 아니라 1,2,3 이면 '123' 으로 나오는 숫자들의 조합의 합을 구해야 한다.
이때 이진트리에서 깊이가 깊어질수록 노드의 값에 10 을 해주면 10의 자리씩 증가하므로, 1->2->3 인 경우 1-2는 110+2 = 12
2->3은 12*10 + 3= 123 으로 원하는 숫자로 만들 수 있다.
즉, 루트 노드에서 터미널 노드까지 dfs를 통해서 내려가면서, 해당 합들을 업데이트하고, 모든 노드를 탐색한 후에 업데이트한 합을 반환한다.
Code
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
def dfs(node, curNum):
if node:
if not node.left and not node.right:
return curNum*10 + node.val
total = 0
total += dfs(node.left, curNum*10+node.val)
total += dfs(node.right, curNum*10+node.val)
return total
else:
return 0
return dfs(root, 0)Complexicity
시간 복잡도
주어진 이진 트리의 모든 노드를 탐색하므로 노드의 개수가 n이라고 했을 때, 시간 복잡도는 O(n)이 소요된다.
공간 복잡도
dfs를 통한 재귀 탐색을 진행하므로, 최악의 경우 이진 트리의 깊의 만큼의 공간 복잡도가 필요하다. 공간 복잡도는 O(n)이다.
