[link](https://leetcode.com/problems/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
Explanation: The root-to-leaf path with the target sum is shown.

#### Example 2:


Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

#### Example 3:

Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

#### Constraints:

- The number of nodes in the tree is in the range [0, 5000].
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000

---

Inside the hasPathSum function, there is a nested helper function called dfs, which stands for depth-first search. This function performs a recursive depth-first search traversal of the binary tree.

The dfs function takes two parameters: node, representing the current node being traversed, and curSum, representing the current sum of values along the path from the root to the current node.

If the current node is None (indicating an empty subtree), the function returns False, as there is no path to continue.

If the current node is not None, its value is added to the curSum variable.

Next, the function checks if the current node is a leaf node, meaning it has no children (left or right). If this condition is satisfied, the function checks if the targetSum is equal to the curSum. If they are equal, it means that a path from the root to this leaf node has been found with the desired sum, so the function returns True. Otherwise, it returns False.

If the current node is not a leaf node, the function recursively calls itself twice, once for the left child of the current node (dfs(node.left, curSum)) and once for the right child of the current node (dfs(node.right, curSum)).

The result of the recursive calls is combined using the logical OR (or) operator. If either of the recursive calls returns True, it means that a path with the desired sum has been found in either the left subtree or the right subtree. In that case, the function returns True. If both recursive calls return False, indicating no path with the desired sum has been found in either subtree, the function returns False.

#### Solution 1

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def dfs(node, curSum):
            if not node:
                return False

            curSum += node.val
                
            if not node.left and not node.right:
                return targetSum == curSum
            
            return (dfs(node.left, curSum) or dfs(node.right, curSum))

        return dfs(root, 0)
        

O(T): O(N)
O(S): O(H)