[LeetCode] 129. Sum Root to Leaf Numbers (Daily Question)

문제

---

 

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.
    - For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

 

이진트리가 주어졌을 때, leaf노드에서 이어붙인 값의 합을 구하는 문제이다.

이어붙인 값이란, 부모 노드의 값과 자식 노드의 값을 이어 붙이는 과정을 반복한 값을 의미한다.예를 들면, 루트 노드에서 leaf노드로 가는 경로의 값이 1, 2, 3일때 이어붙인 값은 123이 된다.

 

Example 1:

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

 

풀이

---

아이디어

이어붙인 값은 (부모노드의 이어붙인 값 * 10 + 현재 노드의 값)으로 나타낼 수 있다.

재귀함수로 트리를 순회하며 값을 이어붙여준다.

 

코드

# 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: Optional[TreeNode], stack: int = 0) -> int:
        sm = 0
        # 부모 노드의 값과 이어붙임
        stack = stack*10 + root.val

        # leaf노드인 경우 값 반환
        if root.left is None and root.right is None:
            return stack
        
        # 좌측 자식 노드 탐색
        if root.left is not None:
            sm += self.sumNumbers(root.left, stack)
        # 우측 자식 노드 탐색
        if root.right is not None:
            sm += self.sumNumbers(root.right, stack)

        return sm

---

 

후기

---

난이도

재귀함수만 쓸 줄 안다면 쉽게 풀 수 있는 문제이다.

문제 이해, 아이디어, 구현, 예외 사항 모두 쉽게 생각할 수 있다.

 

다른 풀이

값을 이어붙일 때 문자열로 이어붙일 수도 있다.