112. 路径总和

var hasPathSum = function(root, targetSum) {
  if (!root) return false
  let is = false

  dfs(root, 0)

  function dfs(node, num) {
    if (!node.left && !node.right) {
      if (is) return
      if (num + node.val === targetSum) is = true
      return
    }

    node.left && dfs(node.left, num + node.val)
    node.right && dfs(node.right, num + node.val)
  }

  return is
}
console.log(
  hasPathSum(
    {
      val: 5,
      left: {
        val: 4,
        left: {
          val: 11,
          left: {
            val: 7,
          },
          right: {
            val: 2,
          },
        },
      },
      right: {
        val: 8,
        left: {
          val: 13,
        },
        right: {
          val: 4,
          right: {
            val: 1,
          },
        },
      },
    },
    22
  )
)

console.log(
  hasPathSum(
    {
      val: 1,
      left: {
        val: 2,
      },
    },
    1
  )
)