---
title: "112. Path Sum"
url: "https://laigary.com/interview/coding/112-path-sum"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-26"
tags: ["Tree", "Depth-First Search"]
---

# 112. Path Sum

[112\. Path Sum](https://leetcode.com/problems/path-sum/)

問有沒有一條**從根到葉**的路徑，節點值加起來剛好等於 `targetSum`。

## 思路

這個題目很像是 N Sum 的題目，不過是從根節點開始，找到是不是可以從根節點到葉節點之間，所有的值加起來剛好和目標相同。

作法是**一路往下把目標扣掉**：走到某個節點時，把 `targetSum` 減去它的值再傳給子節點。這樣「累加和是否等於目標」就變成「**走到葉節點時目標剛好歸零**」，不需要另外維護一個累加變數。

### base case 有兩個條件，缺一不可

這題唯一的陷阱在終止條件：

```python
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](/interview/coding/111-minimum-depth-of-binary-tree) 是同一個經典陷阱。

### 三題的階梯

這題是 Path Sum 家族的入門，三題各自放寬了一個東西：

| | 起點 | 終點 | 要回傳什麼 | 新增的難點 |
|---|---|---|---|---|
| **112 這題** | 根 | 葉 | 存不存在（`bool`） | — |
| [113. Path Sum II](/interview/coding/113-path-sum-ii) | 根 | 葉 | **所有**路徑（`list`） | 要**回溯**（記路徑、離開時還原） |
| [437. Path Sum III](/interview/coding/437-path-sum-iii) | **任意** | **任意** | 數量（`int`） | **端點放寬** → 要枚舉起點 |

## 解題方向

```python
# 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](/interview/coding/100-same-tree) 用 `and`（兩邊都要成立）剛好相反 —— **「存在」用 `or`、「全部」用 `and`**，這組對照很好記。

## 補充

**節點值可以是負數**（題目沒有保證非負），所以**不能靠「剩餘目標小於 0 就剪枝」**。這是很多人會加的優化，但在有負數的樹上會漏掉答案 —— 往下走可能先變小再變大。

**同一家族的其他題**（都是根到葉，只是輸出不同）：

- [113. Path Sum II](/interview/coding/113-path-sum-ii) —— 列出所有符合的路徑
- [257. Binary Tree Paths](/interview/coding/257-binary-tree-paths) —— 列出所有根到葉路徑（不管總和）
- [129. Sum Root to Leaf Numbers](/interview/coding/129-sum-root-to-leaf-numbers) —— 把每條路徑當成一個數字再加總
- [437. Path Sum III](/interview/coding/437-path-sum-iii) —— 路徑不必從根開始也不必在葉結束

整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

## 複雜度

- 時間 $O(n)$ — 最壞情況要走完每個節點；找到答案會短路提早返回
- 空間 $O(h)$ — 遞迴堆疊，`h` 是樹高

其中 `n` 是節點數、`h` 是樹高（平衡樹 $O(\log n)$、退化成鏈時 $O(n)$）。

這題**不需要額外空間存路徑**，因為只要回答存不存在 —— 這正是它比 [113](/interview/coding/113-path-sum-ii) 簡單的地方。