LeetCode Path Sum：遞歸判斷二叉樹根到葉路徑和

題目大意

給定二叉樹根節點 root 與目標和 targetSum。判斷是否存在從根節點到葉子節點的路徑，使得路徑上所有節點值之和等於 targetSum。存在回傳 true，否則 false。

範例：

    3
   / \
  9  20
    /  \
   15   7
  /
 14
targetSum = 12 → true (路徑 3→9)

解法：遞歸減法思路

遞歸進入節點時，將目標值減去當前節點值：remaining = targetSum - node.val。若到達葉子節點且 remaining == 0，找到有效路徑。否則遞歸檢查左右子樹。

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: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        targetSum -= root.val
        if targetSum == 0 and not root.left and not root.right:
            return True
        return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)

C++ 完整實現

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        targetSum -= root->val;
        if (targetSum == 0 && !root->left && !root->right) return true;
        return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
    }
};

關鍵點

• 空樹回傳 false。
• 必須是葉子節點（左右子節點皆為空）且剩餘和為 0。中間節點和為 0 不算。
• 遞歸參數直接傳遞更新後的 targetSum，無需額外累加變數。

複雜度

• 時間：O(N)，每個節點訪問一次。
• 空間：O(H) 遞歸棧深度，H 為樹高。最壞 O(N)（退化鏈），平均 O(log N)（平衡樹）。

延伸：Path Sum II / III

• Path Sum II (113)：找出所有符合條件的路徑（需回溯收集路徑）。
• Path Sum III (437)：路徑不必從根開始，任意節點向下路徑和等於目標（前綴和 + 哈希表優化）。