51: Binary tree path sum 2

Given a binary tree and sum. Calculate how many paths have sum equals to the given sum

Note: a path can go down from parent to any child

 

Example 1

Input:        8    sum = 10 
             / \
            2   3
           /   / \
          4   5  -1
             /  
            2 

Output: 3

Explanation: 8 -> 2, 8 -> 3 -> -1, 3 -> 5 -> 2

Example 2

Input:     2   sum = 5
          / \  
         5   3 

Output: 2

Explanation: 5 and 2 -> 3