112. Path Sum

题目

给定一个二叉树的根节点 root 和 targetSum，如果这个树从根节点到叶子节点的和与目标值相等，返回 true。

解析

从整体上来看，一个二叉树是否具有目标值 f(node)，取决于f(node.left) || f(node.right)
为了计算路径和，需要传递已知的路径和。函数原型为
f(sum, node) bool

伪代码

if node == nil
  return false
if node is leaf
  return target == sum+node.val
return f(sum+node.val, node.left) || f(sum+node.val node.right)

代码

func hasPathSum(root *TreeNode, targetSum int) bool {
    return f(targetSum, 0, root)
}

func f(target int, sum int, node *TreeNode) bool {
    if node == nil {
        return false
    }
    if node.Left == nil && node.Right == nil {
        return target == sum + node.Val
    }
    return f(target, sum+node.Val, node.Left) || f(target, sum+node.Val, node.Right)
}

image.png