A video game has a level shaped like a binary tree of rooms. You enter at the root room and can only move down, from a room to one of its children. Each room gives a number of points, which can be negative. A dead-end room, with no child, is called a leaf.
A route starts at the root and ends at a leaf. Return true if some route has a total of exactly targetSum points. Otherwise, return false. A route that stops at a room that still has a child does not count. An empty tree has no route.
Return true or false.
How the judge passes the data
Examples
Example 1:
Input: root = [7,3,9,1,null,null,5], targetSum = 11
Output: true
Explanation: The route 7 -> 3 -> 1 ends at a leaf, and 7 + 3 + 1 = 11.
Example 2:
Input: root = [7,3,9,1,null,null,5], targetSum = 10
Output: false
Explanation: The route 7 -> 3 adds up to 10, but room 3 still has a child (room 1), so the route is not complete.
Example 3:
Input: root = [5], targetSum = 5
Output: true
Explanation: The tree is a single room. It has no child, so it is a leaf, and the route of one room scores 5.