###### tags: `Leetcode` `medium` `tree` `dfs` `python`

# 113. Path Sum II

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

## 題目:
Given the ```root``` of a binary tree and an integer ```targetSum```, return all **root-to-leaf** paths where the sum of the node values in the path equals ```targetSum```. Each path should be returned as a list of the node **values**, not node references.

A **root-to-leaf** path is a path starting from the root and ending at any leaf node. A **leaf** is a node with no children.


#### [圖片來源:] https://leetcode.com/problems/path-sum-ii/

## 解題想法:
* 題目為求root到leaf之path，其路徑和為target
* dfs深度搜尋!!
* 傳遞當前path、當前總和

## Python:

class TreeNode(object):
    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: List[List[int]]
        """
        self.res=[]
        self.dfs(root,targetSum,[],0)
        return self.res
    def dfs(self,root,targetSum,path,cur_sum):
        if not root:
            return 
        if not root.left and not root.right:
            #判斷是否==target
            if (cur_sum+root.val)==targetSum:
                self.res.append(path+[root.val])
            return
        cur_sum+=root.val
        self.dfs(root.left,targetSum,path+[root.val],cur_sum)
        self.dfs(root.right,targetSum,path+[root.val],cur_sum)

        '''
        對於傳遞參數的path+[root.val]:
        不能像cur_sum+=root.val直接更動
        錯誤: path.append(root.val) 
        正確: 新創一條path:  newPath=list(path)  newPath.append(root.val)
        self.dfs(root.left,targetSum,newPath,cur_sum)
        self.dfs(root.right,targetSum,newPath,cur_sum)
        '''

root = TreeNode(5)
root.insertLeft(4)
root.insertRight(8)
root.left.insertLeft(11)
root.left.left.insertLeft(7)
root.left.left.insertRight(2)
root.right.insertLeft(13)
root.right.insertRight(4)
root.right.right.insertLeft(5)
root.right.right.insertRight(1)
root.printTree()
result = Solution()
ans = result.pathSum(root,22)
print(ans)