112. Path Sum

-
https://leetcode.com/problems/path-sum/

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
---
Intuition
Base case - If node is null, no path exists - return false
Since we are returning false, and problem statement requires existence of a path, we will 
  1. Explore each path to the end => DFS => recursion
  2. Combine results of exploring each path with an OR operation
If node is leaf, and value = target => return true
For every other case recurse on left and right child, and combine results with an OR
If node is leaf, and value !=target, recursion will run to null nodes, and results with combine false, or false resulting in false for the left node
---
Related problems
113-path-sum-ii
437-path-sum-iii
---
Time - O(n)
Space - O(n)