# Tree - 113. Path Sum II

113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and `sum = 22`,

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

``````

Return:

``````[
[5,4,11,2],
[5,8,4,5]
]
``````

go：

``````/**

* Definition for a binary tree node.

* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func pathSum(root *TreeNode, sum int) [][]int {
var res [][]int
if root == nil {
return res
}

recursive(root, &res, []int{root.Val}, root.Val, sum)

return res
}

func recursive(node *TreeNode, res *[][]int, incr []int, tempSum int, sum int) {
if node.Left == nil && node.Right == nil {
if tempSum == sum {
*res = append(*res, incr)
}
}

if node.Left != nil {
var incrLeft []int
incrLeft = append(incrLeft, incr...)
incrLeft = append(incrLeft,  node.Left.Val)
recursive(node.Left, res, incrLeft, tempSum + node.Left.Val, sum)
}

if node.Right != nil {
recursive(node.Right, res, append(incr, node.Right.Val), tempSum + node.Right.Val, sum)
}
}
``````

Nothing just happens, it's all part of a plan.