Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:

Given the below binary tree and sum = 22,

5             / \            4   8           /   / \          11  13  4         /  \    / \        7    2  5   1

return

[   [5,4,11,2],   [5,8,4,5]]

 

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 List
     
      
       > pathSum(TreeNode root, int sum) {12          List
       
        
         > result=new ArrayList
         
          
           >();13 List
           
             tmp=new ArrayList
            
             ();14 dfs(result,tmp,sum,root,0);15 return result;16 }17 18 private void dfs(List
             
              
               > result, List
               
                 tmp, int sum, TreeNode root, int curSum) {19 // TODO Auto-generated method stub20 if(root==null)21 return;22 if(root.left==null&&root.right==null){23 if(curSum+root.val==sum){24 tmp.add(root.val);25 result.add(new ArrayList
                
                 (tmp));26 tmp.remove(tmp.size()-1);27 return;28 }29 return;30 }31 tmp.add(root.val);32 dfs(result,tmp,sum,root.left,curSum+root.val);33 dfs(result,tmp,sum,root.right,curSum+root.val);34 tmp.remove(tmp.size()-1);35 }36 }