Path Sum
You are given the root of a binary tree and an integer targetSum. Return true if the tree has a root-to-leaf path whose values add up to exactly targetSum, and false otherwise.
A root-to-leaf path starts at the root and ends at a leaf, a node with no children. Stopping partway down does not count, even if the sum matches at that point.
Node values and the target can be negative, so the running sum can go down as well as up.
Constraints
- The tree has between
0and5000nodes. -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
Examples
Example 1
Input: root = [3,9,6,-2,null,1,4,null,5], targetSum = 15 Output: true
The path 3 → 9 → -2 → 5 ends at a leaf and adds up to 15.
Example 2
Input: root = [3,9,6,-2,null,1,4,null,5], targetSum = 12 Output: false
3 + 9 = 12, but 9 is not a leaf. The complete paths sum to 15, 10 and 13.
Example 3
Input: root = [], targetSum = 0 Output: false
An empty tree has no root-to-leaf path at all, not even one that sums to 0.
JavaScript you'll use: Recursion, the call stack and memoization Linked list and tree nodes
/**
* Tree nodes are provided (you don't need to define them):
* class TreeNode { constructor(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }
*/
/**
* @param {TreeNode | null} root
* @param {number} targetSum
* @return {boolean}
*/
function hasPathSum(root, targetSum) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.