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

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

DFS ＋ tree 時常使用遞迴法求解

1. Repeat（題目重複確認）

• 輸入：二元樹的 root，一個整數targetSum
• 輸出：如果找得到一條從 root 到 leaf 的路徑總和為目標總和，則返回 true

2. Examples（舉例確認理解）

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
5+4+11+2 = 22

Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

3. Approach（解題思路）

方法 1：遞迴法（有輔助函數）

• 解題想法：經過的每一步都減去節點值，如果走到 leaf，目標值已經歸零，則表示經過的這條路徑總和為目標和，能找到滿足的路徑，返回 true。
• 時間複雜度：O(n)，其中 n 是樹的節點數，因為每個節點都會被訪問一次，DFS 必須探索所有可能的根到葉路徑。
• 空間複雜度：O(h) ，最傾斜的樹複雜度最高，tree travesal 的題目空間複雜度通常為樹高

方法 2：遞迴法（更簡潔）

• 空節點要設為 false
• 遞迴檢查以 root 的左子點及右子點的路徑，如果走到 leaf，則檢查目標值是否歸零，如果是，則返回 true

4. Code（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:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == nullptr)
            return false;
        return dfs(root, targetSum);
    }

private:
    bool dfs(TreeNode* node, int remainingsum){
        if(node == nullptr)
            return false;
        remainingsum -= node->val; //減去正在經過的節點值
				
				//左右子樹都是空指標，該點則為 leaf
        if(node->left == nullptr && node->right == nullptr){
            return remainingsum == 0; // 如果是葉子節點且剩餘和為 0，表示找到了目標路徑
        }
        // 遞迴檢查左子樹或右子樹
        // 只要其中一條路徑滿足條件就返回 true
        return dfs(node->left, remainingsum) || dfs(node->right, remainingsum);
    }
};

＃不使用輔助函數
class SolutionAlternative {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        // 空節點返回 false
        if (root == nullptr) {
            return false;
        }
        
        // 更新目標和（減去當前節點值）
        targetSum -= root->val;
        
        // 如果是葉子節點，檢查剩餘和是否為 0
        if (root->left == nullptr && root->right == nullptr) {
            return targetSum == 0;
        }
        
        // 遞迴檢查左右子樹
        return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
    }
};

5. Test 範例

6. 相關題目與延伸概念

• 113. Path Sum II：找所有從 root 到 leaf 的路徑，並且該路徑的總和等於目標和
• 124. Binary Tree Maximum Path Sum：找出二元樹中總和最大的路徑，這題與 path sum 類似

7. 補充：語法＆注意事項

• nullptr 判斷：
  • if(root == nullptr) 用來處理空樹的情況，當root 為空時直接返回 false。
• dfs 遞迴函式/targetSum 更新：
  • 遞迴過程中，從 root 開始，不斷將目標值減去當前節點的值，並檢查到達葉子節點時是否達到目標值 0。
• 葉子節點的判斷：
  • if(node->left == nullptr && node->right == nullptr)，這一判斷用來檢查節點是否是葉子節點，葉子節點是沒有子節點的節點。

ps. 部分內容經 AI 協助整理