###### tags: `Leetcode` `medium` `tree` `dfs` `python` `c++` `Top 100 Liked Questions`

# 437. Path Sum III

## [題目連結:] https://leetcode.com/problems/path-sum-iii/

## 題目:
Given the ```root``` of a binary tree and an integer ```targetSum```, return the number of paths where the sum of the values along the path equals ```targetSum```.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).


## 解題想法:
* 此題為求二元樹中，任一頂點往下的路徑中，有多少條路徑和為targetSum
* 使用DFS遞迴
* 主函式為def pathSum(root, targetSum)
* 自訂函式def dfs(curRoot, curSum):
* 當前要拜訪的節點, 目標和
* **需注意**: 有三種可能的case
* Case1: 含當前root開始遍歷可以找到的路徑數
* dfs(root, targetSum)
* Case2: 當前root之左子數遞迴
* path(root.left, targetSum)
* Case3: 當前root之右子數遞迴
* path(root.right, targetSum)
* **三種case加總才為最終解**

## Python:

class TreeNode():
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def pathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: int
        """
        if not root:
            return 0
        return self.dfs(root,targetSum)+self.pathSum(root.left,targetSum)+self.pathSum(root.right,targetSum)
    def dfs(self,root,targetSum):
        res=0
        if not root:
            return res
        targetSum-=root.val
        if targetSum==0:
            res+=1
        res+=self.dfs(root.left,targetSum)
        res+=self.dfs(root.right,targetSum)
        return res


root=TreeNode(10)
root.insertLeft(5)
root.insertRight(-3)
root.left.insertLeft(3)
root.left.insertRight(2)
root.right.insertRight(11)
root.left.left.insertLeft(3)
root.left.left.insertRight(-2)
root.left.right.insertRight(1)
root.printTree()

result=Solution()
ans=result.pathSum(root,targetSum=8)
print(ans)

## C++:
* 因為有給極端的test case, 若用int會編譯失敗
* 改用long long [https://blog.csdn.net/CV_Jason/article/details/85244813]

/**
 * 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 pathSum(TreeNode* root, int targetSum) {
        if (root==nullptr)
            return 0;
        // use 'int' cause signed integer overflow :"(
        return dfs(root,(long long) targetSum)+ pathSum(root->left, targetSum)+pathSum(root->right, targetSum);
    }

    int dfs(TreeNode *root, long long curSum){
        if (root==nullptr)
            return 0;
        int res=0;
        //use long long correct
        curSum-=root->val;
        if (curSum==0)
            res+=1;
        res+=dfs(root->left, curSum)+dfs(root->right, curSum);
        return res;
    }
};