資訊

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

---

目錄

• 資訊
• 目錄
• 題目
• 解法
  • 概念
  • 程式碼
• 複雜度
  • 時間複雜度
  • 空間複雜度

---

題目

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:

• 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.

Constraints:

• 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)$