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)
}
}
|