# 113 Path Sum II

Given the `root` of a binary tree and an integer `targetSum`, return all root-to-leaf paths where each path's sum equals `targetSum`.

A leaf is a node with no children.

Example 1:

``````      5
/ \
4   8
/   / \
11  13  4
/  \    / \
7    2  5   1

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

Example 2:

``````    1
/ \
2   3

Input: root = [1,2,3], targetSum = 5
Output: []
``````

Example 3:

``````Input: root = [1,2], targetSum = 0
Output: []
``````

Constraints:

• The number of nodes in the tree is in the range `[0, 5000]`.
• -1000 <= `Node.val` <= 1000
• -1000 <= `targetSum` <= 1000
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 `````` ``````# 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]: res = [] def dfs(node, path, total): if not node: return new_val = node.val + total new_path = path + [node.val] if node.left == node.right and new_val == targetSum: res.append(new_path) return dfs(node.left, new_path, new_val) dfs(node.right, new_path, new_val) dfs(root, [], 0) return res``````
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 `````` ``````/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func pathSum(root *TreeNode, targetSum int) [][]int { var result [][]int sum(root, targetSum, 0, nil, &result) return result } func sum(t *TreeNode, target, curSum int, curPath []int, result *[][]int) { if t == nil { return } curPath = append(curPath, t.Val) if t.Left == nil && t.Right == nil { if curSum+t.Val == target { // Important! // func arg curPath is a slice reference // its underlying data could be changed in another resursion // so we make a copy res := make([]int, len(curPath)) copy(res, curPath) *result = append(*result, res) } return } if t.Left != nil { sum(t.Left, target, curSum+t.Val, curPath, result) } if t.Right != nil { sum(t.Right, target, curSum+t.Val, curPath, result) } }``````