437. Path Sum III

📘 題目敘述

給你一棵二元樹的根節點 root，以及一個整數 targetSum。

請回傳路徑總和等於 targetSum 的路徑數量。

路徑不需要從根節點開始，也不需要在葉節點結束，但路徑方向必須是往下走（只能從父節點走到子節點）。

條件限制

樹中節點數量在範圍 [0, 1000]
-10^9 <= Node.val <= 10^9
-1000 <= targetSum <= 1000

🧠 解題思路

我這份寫法的想法是：我在 DFS 走到某個節點時，把「從根走到目前節點的路徑」用一個容器記下來，然後在這個節點當結尾，去檢查有多少段「往上回推的連續路徑」加起來等於 targetSum。

具體來說：

nums 裡面存的是「目前 DFS 路徑上，從根到現在」每個節點的值
當我走到某個節點 root，我把 root->val push 進 nums
然後我從 nums 的尾巴開始往前加總：這個加總代表「以目前節點為結尾的所有向下路徑」的總和

只要累積和 sum 等於 targetSum，就代表存在一條合法路徑（起點可能在路徑中間，不一定是根），所以我把 c++。

這樣每個節點都做一次「往上回推」的檢查，就能把所有可能路徑都數到。

所有變數

root：題目輸入的樹根節點（也是 DFS 目前走到的節點）
targetSum：題目輸入的目標總和
target：我用 long long 存的目標值（避免加總溢位）
c：符合條件的路徑數量（全域累加）
nums：目前 DFS 路徑上每個節點的值（從根到當前節點）

🪜 主要流程步驟

1. 用 DFS 維護一條「從根到目前節點」的路徑序列

我寫 count(root, nums)，nums 代表目前 DFS 走到這裡的路徑值序列。每往下走到一個節點，就把它的值 push 進去；回來時再 pop 掉，讓 nums 永遠對應到目前遞迴堆疊上的那條路。

2. 每到一個節點，就把它當作「路徑結尾」往回檢查

當 root 不為空時：

先把 root->val 放進 nums
設 sum = 0
從 nums 最後一個元素開始一路往前加，這代表我在枚舉所有「以目前節點結尾」的向下路徑
只要某次累加後 sum == target，就代表找到一條符合的路徑，c++

3. 遞迴左右子樹，繼續用同樣方式數路徑

檢查完「以目前節點結尾」的路徑後，我再遞迴呼叫：

count(root->left, nums)
count(root->right, nums)

這樣每個節點都會被當作結尾檢查一次，所有路徑都會被數到。

4. 回溯時把目前節點從 nums 移除

左右子樹都做完後，nums.pop_back()，把這個節點值移掉，回到上一層時 nums 才會是正確的路徑。

5. 在 pathSum 裡設定 target 並從根開始 DFS

pathSum(root, targetSum) 會先把 target 設好，然後用空的 nums 從根開始 DFS，最後回傳累加的 c。

💻 程式碼實作

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    int c = 0;
    long long target;
    void count(TreeNode* root, deque<int>& nums) {
        long long sum = 0;
        if (root) {
            nums.push_back(root->val);
            for (int i = nums.size() - 1; i >= 0; i--) {
                sum += nums[i];
                if (sum == target) {
                    c++;
                }
            }
            count(root->left, nums);
            count(root->right, nums);
            nums.pop_back();
        } else {
            return;
        }
    }

    int pathSum(TreeNode* root, int targetSum) {
        target = targetSum;
        deque<int> nums = {};
        count(root, nums);
        return c;
    }
};

🔗 題目連結

https://leetcode.com/problems/path-sum-iii/