// 112. Path Sum

//

// Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

// A leaf is a node with no children.

// Example 1:

// Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

// Output: true

// Example 2:

// Input: root = [1,2,3], targetSum = 5

// Output: false

// Example 3:

// Input: root = [1,2], targetSum = 0

// Output: false

// Constraints:

// The number of nodes in the tree is in the range [0, 5000].

// -1000 <= Node.val <= 1000

// -1000 <= targetSum <= 1000

//

// Runtime: 0 ms, faster than 100.00% of Java online submissions for Path Sum.

// Memory Usage: 39.2 MB, less than 12.37% of Java online submissions for Path Sum.

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode() {}

* TreeNode(int val) { this.val = val; }

* TreeNode(int val, TreeNode left, TreeNode right) {

* this.val = val;

* this.left = left;

* this.right = right;

* }

* }

*/

class Solution {

public boolean hasPathSum(TreeNode root, int targetSum) {

if (Objects.isNull(root)) return false;

if (Objects.isNull(root.left) && Objects.isNull(root.right) && root.val == targetSum) return true;

return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);

}

}