112. Path Sum
問有沒有一條從根到葉的路徑，節點值加起來剛好等於 targetSum。
思路
這個題目很像是 N Sum 的題目，不過是從根節點開始，找到是不是可以從根節點到葉節點之間，所有的值加起來剛好和目標相同。
作法是一路往下把目標扣掉：走到某個節點時，把 targetSum 減去它的值再傳給子節點。這樣「累加和是否等於目標」就變成「走到葉節點時目標剛好歸零」，不需要另外維護一個累加變數。
base case 有兩個條件，缺一不可
這題唯一的陷阱在終止條件：
if root.val == targetSum and not root.left and not root.right:
必須同時檢查「值對得上」和「這是葉節點」。 只檢查前者的話，路徑走到一半剛好湊到目標就會回傳 True，但題目要求一定要走到葉節點。
例如 [1, 2]（根 1、左子 2）找 targetSum = 1：根節點的值剛好等於 1，但它不是葉節點，答案應該是 False。少了葉節點判斷就會錯。
反過來，「葉節點」也不能只靠 not root 來判斷。 用「走到 None 時檢查目標是否為 0」看似可行，但單邊子樹為空的節點會被誤判成葉節點 —— 這和 111. Minimum Depth 是同一個經典陷阱。
三題的階梯
這題是 Path Sum 家族的入門，三題各自放寬了一個東西：
| 起點 | 終點 | 要回傳什麼 | 新增的難點 | |
|---|---|---|---|---|
| 112 這題 | 根 | 葉 | 存不存在（bool） | — |
| 113. Path Sum II | 根 | 葉 | 所有路徑（list） | 要回溯（記路徑、離開時還原） |
| 437. Path Sum III | 任意 | 任意 | 數量（int） | 端點放寬 → 要枚舉起點 |
解題方向
# 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: TreeNode, targetSum: int) -> bool:
if not root:
return False
if root.val == targetSum and not root.left and not root.right:
return True
return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)
if not root: return False 處理兩件事：空樹，以及走到某個節點的空子樹。回傳 False 是對的 —— 一條不存在的路徑不可能滿足條件。
最後用 or 連接左右，任何一邊找到就算成功，而且 Python 的 or 會短路：左子樹找到就不會再走右子樹。這和 100. Same Tree 用 and（兩邊都要成立）剛好相反 —— 「存在」用 or、「全部」用 and，這組對照很好記。
補充
節點值可以是負數（題目沒有保證非負），所以不能靠「剩餘目標小於 0 就剪枝」。這是很多人會加的優化，但在有負數的樹上會漏掉答案 —— 往下走可能先變小再變大。
同一家族的其他題（都是根到葉，只是輸出不同）：
- 113. Path Sum II —— 列出所有符合的路徑
- 257. Binary Tree Paths —— 列出所有根到葉路徑（不管總和）
- 129. Sum Root to Leaf Numbers —— 把每條路徑當成一個數字再加總
- 437. Path Sum III —— 路徑不必從根開始也不必在葉結束
整理見 Tree 遍歷模板。
複雜度
- 時間 — 最壞情況要走完每個節點；找到答案會短路提早返回
- 空間 — 遞迴堆疊，
h是樹高
其中 n 是節點數、h 是樹高（平衡樹 、退化成鏈時 ）。
這題不需要額外空間存路徑，因為只要回答存不存在 —— 這正是它比 113 簡單的地方。