# Tree - 112. Path Sum

112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path 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       1

``````

return true, as there exist a root-to-leaf path `5->4->11->2` which sum is 22.

go：

``````/**

* Definition for a binary tree node.

* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func hasPathSum(root *TreeNode, sum int) bool {
var res bool
if root == nil {
return false
}
recursive(root, &res, root.Val, sum)
return res
}

func recursive(node *TreeNode, res *bool, val int, sum int) {
if node.Left == nil && node.Right == nil && val == sum {
*res = true
}

if node.Left != nil {
recursive(node.Left, res, node.Left.Val + val, sum)
}

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

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