[LeetCode] Python - 129. Sum Root to Leaf Numbers

https://leetcode.com/problems/sum-root-to-leaf-numbers/

Sum Root to Leaf Numbers - LeetCode

생각

Leetcode 트리 문제를 계속 풀다보니 base case만 잘 생각해내면 된다라는 자신감을 얻었습니다ㅎㅎ

leaf node까지 가면서 거쳐온 노드들을 차례대로 붙여준다음 이를 누적합으로 계산하는 문제입니다.

 

다음 레벨로 갈 경우 현재까지 거쳐온 비용*10을 하여 자릿수를 높여주고 현재 노드의 값을 더해주면 됩니다. 노드의 값은 일의 자리 숫자라는 제약사항이 있기 때문에 이 방식이 가능한것입니다.

 

이러한 작업을 leaf node 까지 진행해줍니다. 여기서 기저조건이 나오게 됩니다.

 

기저조건은 두가지로 다음과 같습니다.

 

1. leaf node 라면 비용을 계산하여 리턴

2. 노드가 null 일경우 0을 리턴

 

Python Code

# Definition for a binary tree node.
# 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: TreeNode) -> int:
        
        def dfs(root, cost):
            if not root:
                return 0
            
            if not root.left and not root.right:
                return cost*10 + root.val
            
            return dfs(root.left, cost*10+root.val)+dfs(root.right, cost*10+root.val)
            
        return dfs(root, 0)