112. 路径总和（简单）
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例：
给定如下二叉树，以及目标和 sum = 22，
**5** / **4** 8 / / **11** 13 4 / 7 **2** 1
分析：
二叉树的结构非常适合递归，我们从根结点开始一直到叶子结点，必须在叶子结点满足要求时才是正确答案。沿着路径向下时，必须把路径和作为状态转移下去，因此就有了一个递归函数的模型：
def checkSum(root TreeNode, cur int) -> bool:
return checkSum(root.left, cur + root.val) or checkSum(root.right, cur + root.val)
继续考虑跳出条件，当前结点为叶子结点时递归必须停止，当前结点为空时，递归也不可以继续下去。因此加入：
if not root:
return None
if not root.left and not root.right:
if cur + root.Val == sum:
return True
代码（Golang）：
func hasPathSum(root *TreeNode, sum int) bool {
var checkSum func(root *TreeNode, sum int) bool
checkSum = func(root *TreeNode, cur int) bool {
if root == nil {
return false
}
if root.Val + cur == sum && root.Left == nil && root.Right == nil {
return true
}
return checkSum(root.Left, cur + root.Val) || checkSum(root.Right, cur + root.Val)
}
return checkSum(root, 0)
}