# 資訊

:::info
- Question: 129. Sum Root to Leaf Numbers
- From: Leetcode Daily Challenge 2024.04.15
- Difficulty:
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

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.

> Example 1:
:::success
* 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:
:::success
* 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.
:::

> Constraints:
:::success
* The number of nodes in the tree is in the range `[1, 1000]`.
* 0 <= `Node.val` <= 9
* The depth of the tree will not exceed 10.
:::

---

# 解法

## 概念

一樣是 DFS，這次多了 path 的概念，沿路要一直記住 path，最後當遇到 leaf 再把整條轉成 int，至於為什麼又有 `__init__` 的局？因為我不想在 function 裡面帶一堆參數，乾脆給 `__init__` 帶著就好

## 程式碼

# 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 __init__(self):
        self.sum = 0
    def dfs(self,root: TreeNode, path: str):
        path_ = path + str(root.val)
        if not root.left and not root.right:    # leaf
            self.sum += int(path_)
        else:
            if root.left:
                self.dfs(root.left, path_)
            if root.right:
                self.dfs(root.right, path_)
        return
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        self.dfs(root,'')
        return self.sum

---

# 複雜度

## 時間複雜度

走訪過每個點，所以是 $O(n)$


## 空間複雜度

這邊比較麻煩的是空間，因為有 path 的紀錄，而每一層都會換一個 path，有點像是 $O(n^2)$