###### tags: `LeetCode` `Tree` `Recursion` `Medium`
# LeetCode #437 [Path Sum III](https://leetcode.com/problems/path-sum-iii/)
### (Medium)(第一次沒做出來)
給定一個二元樹的根節點 root ，和一個整數 targetSum ，求該二元樹里節點值之和等於 targetSum 的 路徑 的數目。

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

---
這題需要一個額外函式count輔助, 計算以某個節點為起始節點開始的所有可能和。count函式本身為遞迴函式, 但同時, 原本的pathSum函式也是遞迴函是, 目標為指定所有節點為起始節點。因此, 本題是兩個遞迴函式的搭配題。

---

class Solution {
public:
    int ans=0;
    int pathSum(TreeNode* root, int targetSum) {
        if(!root)return 0;
        return count(root, 0, targetSum)+pathSum(root->left, targetSum)+pathSum(root->right, targetSum);
        //這邊的count()是計算以root為起始節點的所有可能數
        //後面兩個pathSum()的目標則是將其左右子節點設為起始節點
        //這樣下一輪遞迴時count()函式就會分別以左右子節點為起始節點計算可能數
    }
    int count(TreeNode* node, int pre, int &target){
        //這個函式的目的則是計算以node為起始節點的所有可能數
        if(!node)return 0;
        int cur=pre+node->val;
        return (cur==target)+count(node->left, cur, target)+count(node->right, cur, target);
    }
};