1 題目描述


2 解法

看到這題的時候，就想要用 DFS 來解，順序大概是 root -> left 走過的節點都把他串起來，然後再 root -> right。那什麼時候要相加呢？當走到葉子節點（走到底時）的時候，就把這條路徑的數字相加起來就可以了。因此也可以用Recursive來解。

大問題：把每條路徑的數字相加起來。
小問題：假設我們已經走到底了，已經把數字串起來
最小的問題：把已經串完的數字，跟tot做加總，最後返回tot。

首先需要有個可以把每個節點串起來的變數path

1
2
3
4
5
6
def dfs(node, path):
    path = path + str(node.val) # 把每個節點串起來
    if node.left:
        dfs(node.left, path)        # 左子樹走到底
    if node.right:
        dfs(node.right, path)       # 右子樹走到底

當走到leaf節點時，要做加總

1
2
3
4
5
6
7
8
9
def dfs(node, path):
    path = path + str(node.val)
    if not node.left and not node.right:  # 串好後，發現已經走到底
        tot += int(path)                  # 把數字相加
    else:
        if node.left:
            dfs(node.left, path)        
        if node.right:
            dfs(node.right, path)

最後返回加總的數字，以下是完整程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
    tot = 0
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        if root:
            self._sum_numbers(root, '')
            return self.tot
        return 0

    def _sum_numbers(self, root: Optional[TreeNode], path) -> None:
        path += str(root.val)
        if not root.right and not root.left:
            self.tot += int(path)
        else:
            if root.left:
                self._sum_numbers(root.left, path)
            if root.right:
                self._sum_numbers(root.right, path)

你可能會想，一定要使用外部的變數嗎？可以不用，可以直接返回數字，這樣就不用使用外部變數了。

  • 但是我們要往下挖的時候，也就是在遞迴的時候，我們要把目前的數字傳下去，所以我們需要一個變數來記錄目前的數字，那就是cur_sum。
  • 到最底的時候，就要把當前目前的數字返回，把每次觸底返回的結果進行相加ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        if root:
            return self._sum_numbers(root, 0)
        return 0

    def _sum_numbers(self, root: Optional[TreeNode], cur_sum) -> None:
        cur_sum = cur_sum * 10 + root.val
        if not root.left and not root.right:
            return cur_sum  
        else:
            ans = 0 
            if root.left:
                ans += self._sum_numbers(root.left, cur_sum)
            if root.right:
                ans += self._sum_numbers(root.right, cur_sum)
            return ans

3 總結

這題不難，但是也是偷看了一下解答，才寫得出來。大概也是花了30分鐘左右，我有想到要使用DFS，但是卡在最小問題，也就是最後加總的時候不確定該怎麼處裡。後來看了解答，才發想有兩種方式，一種是設定class的變數，讓在遞迴的過程中可以直接對變數進行操作。另一個重要的觀念是，該怎麼在每次遞迴的時候，保留之前走過的訊息（也就是把走過的數字串起來或加總）這個需要在每次遞迴的時候，把串到一半的數字繼續往下傳，這樣才能保留之前的訊息，但是也不用擔心值會在不同遞迴的地方改變，每個遞迴有他自己的cur_sum。