루트 대 리프 번호 합계

root에서 0까지의 숫자만 포함하는 이진 트리의 9가 제공됩니다.

트리의 각 루트-리프 경로는 숫자를 나타냅니다.

예를 들어 루트-리프 경로1 -> 2 -> 3는 숫자123를 나타냅니다.

루트에서 리프까지의 모든 수의 총합을 반환합니다. 답변이 32비트 정수에 맞도록 테스트 케이스가 생성됩니다.

리프 노드는 자식이 없는 노드입니다.

예 1:



입력: 루트 = [1,2,3]
출력: 25
설명:
루트-리프 경로1->2는 숫자12를 나타냅니다.
루트-리프 경로1->3는 숫자13를 나타냅니다.
따라서 sum = 12 + 13 = 25 입니다.

예 2:



입력: 루트 = [4,9,0,5,1]
출력: 1026
설명:
루트-리프 경로4->9->5는 숫자 495를 나타냅니다.
루트-리프 경로4->9->1는 숫자 491을 나타냅니다.
루트-리프 경로4->0는 숫자 40을 나타냅니다.
따라서 sum = 495 + 491 + 40 = 1026 입니다.

제약:

트리의 노드 수가 [1, 1000] 범위에 있습니다.

0 <= Node.val <= 9

트리의 깊이는 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]) -> int:
        paths = [(root, root.val)]
        i = 0
        total = 0
        while i < len(paths):
            curr, val = paths[i]
            if curr:
                if not curr.left and not curr.right:
                    total += val
                if curr.left:
                    paths.append((curr.left, 10 * val + curr.left.val))
                if curr.right:
                    paths.append((curr.right, 10 * val + curr.right.val))
            i += 1
        return total