先簡單回顧一下，今天預計分析的題目： 112. Path Sum

題目連結：https://leetcode.com/problems/path-sum/

題目敘述：

• 會給一個二元樹與目標總和
• 要找一個從 root 到 leaf 的路徑，加總為目標總和
  

測資的 Input/Output

• 若找到 root 到 leaf 的路徑相加的總和為目標值，則回傳 true，反之，回傳 false
  

DFS 遞迴 解法

1. 判斷是否有 Node，若無則回傳 False

if root is None: return False

2. 用遞迴方式實作 DFS 走訪這棵樹：首先計算目前的加總

newSum = prevSum + node.val

3. 緊接著寫終止條件：若是此點為 leaf，檢查目前加總是否等於 targetSum

if node.left is None and node.right is None: return newSum == targetSum

4. 若此點非葉子，若有左 child，則往左 child 走，若 return True 回來，表示有找到符合加總的路徑，便無需往下做，跟著回傳 True

if node.left is not None and dfsFindPath(node.left, newSum): return True

5. 若此點非葉子，若有右 child，則往右 child 走，若 return True 回來，表示有找到符合加總的路徑，便無需往下做，跟著回傳 True

if node.right is not None and dfsFindPath(node.right, newSum): return True

6. 若以上情況都沒有，則回傳 False

return False

• 完整程式碼如下：

# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root is None: return False

        def dfsFindPath(node, prevSum):
            newSum = prevSum + node.val

            if node.left is None and node.right is None: return newSum == targetSum
            if node.left is not None and dfsFindPath(node.left, newSum): return True
            if node.right is not None and dfsFindPath(node.right, newSum): return True
            return False

        return dfsFindPath(root, 0)

DFS 迭代解法

1. 若用迭代實作 DFS，我們需要準備一個 stack，用來紀錄走訪的順序。
2. 首先，先將起點放入 stack 中，同時我們需要紀錄走訪前的加總狀態，才能接續走訪 children。

stack = [(root, 0)]

3. 接下來開始迭代，當 stack 中還有資料，就取一個 node 出來。

node, prevSum = stack.pop()

4. 走訪當前節點，計算新的總和

newSum = prevSum + node.val

5. 若當前節點為葉子，且總和符合目標值，則回傳 True

if node.left is None and node.right is None and newSum == targetSum: return True

6. 若當前節點不為葉子：

   1. 若左側 child 存在，則將其加入 stack 中，待稍後進行走訪。

   if node.left is not None: stack.append((node.left, newSum))
   

   2. 若右側 child 存在，則將其加入 stack 中，待稍後進行走訪。

   if node.right is not None: stack.append((node.right, newSum))
   

7. 若完整迭代完畢，表示沒有找到相符的 path，回傳 False

return False

完整程式碼如下：

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root is None: return False

        stack = [(root, 0), ]
        while stack:
            node, prevSum = stack.pop()
            newSum = prevSum + node.val

            if node.left is None and node.right is None and newSum == targetSum: return True
            if node.left is not None: stack.append((node.left, newSum))
            if node.right is not None: stack.append((node.right, newSum))

        return False