112. Path Sum Leetcode Java

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.

For 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.

Solution:

Recursive solution. 

Notice the path must be root-to-leaf, so we have to determine if current node is leaf and if yes, then check if the sum from root to leaf is the target sum. Otherwise, recursively check its left child and right child. 

  public boolean hasPathSum(TreeNode root, int sum) {  
     if(root==null) return false;  
     if(root.left==null && root.right==null && root.val==sum) return true;  
     return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val);  
   }