Path Sum

Problem:

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:

1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public boolean hasPathSum(TreeNode root, int sum) {  
12:      if(root==null)  
13:       return false;  
14:      if(root.left==null && root.right==null&&root.val==sum)  
15:       return true;  
16:      return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);  
17:    }  
18:  }  

Discussion:
Recursive solution. The path sum of the current node is the path sum of its child nodes plus its value.