Root-to-Leaf Path Sum

Write has_path_sum(root, target) that returns True if the binary tree has a path from the root down to a leaf whose values add up to target, and False otherwise. A leaf is a node with no children. An empty tree has no paths, so it always gives False.

Each node is a Node with a value val and two children, left and right, which are None when missing. The provided build makes a tree from a list of values in level order, where None marks a missing child.

Examples

        6
       / \
      3   9
     / \   \
   -2   4   7
   /
  8

tree = build([6, 3, 9, -2, 4, None, 7, 8])
has_path_sum(tree, 13)  # returns True
has_path_sum(tree, 15)  # returns True
has_path_sum(tree, 9)  # returns False

13 is 6 + 3 + 4, and 15 is 6 + 3 + (-2) + 8. The path 6, 3 also adds up to 9, but the node 3 is not a leaf, so that path stops too early.

Constraints

• 0 to 2,000 nodes; values are integers from -1,000 to 1,000.