Path Sum

A root-to-leaf path starts at the root and follows child links until it reaches a leaf (a node with no children).

Given the root of a binary tree and an integer target, return True if the tree has a root-to-leaf path whose node values add up to target, and False otherwise. An empty tree has no paths.

Examples

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

Input:  root = [5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, 1], target = 22
Output: True
Explanation: 5 -> 4 -> 11 -> 2 sums to 22.

  1
 / \
2   3

Input:  root = [1, 2, 3], target = 5
Output: False
Explanation: The root-to-leaf sums are 3 and 4.

Input:  root = [1, 2], target = 1
Output: False
Explanation: Node 1 is not a leaf; the only path is 1 -> 2 with sum 3.

Constraints

• 0 <= number of nodes <= 1000
• Node values and target may be negative.

Goals

• Pass information downwards through recursive calls (the remaining target)
• Detect a leaf node correctly
• Combine boolean results from two subtrees with or