## 題解

### DFS

# 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:
        self.total = 0
        def dfs(root,sumStr: str):
            if not root:
                return
            if not root.left and not root.right:
                self.total += int(sumStr + str(root.val))
            dfs(root.left,sumStr+str(root.val))
            dfs(root.right,sumStr+str(root.val))
        
        dfs(root,"")

        return self.total

# 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:
        self.total = 0
        def dfs(root: TreeNode, sum: int):
            if not root:
                return
            sum = sum * 10
            if not root.left and not root.right:
                self.total += sum + root.val
            dfs(root.left,sum +root.val)
            dfs(root.right,sum+root.val)
        
        dfs(root,0)

        return self.total