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  * struct TreeNode {  4  *     int val;  5  *     TreeNode *left;  6  *     TreeNode *right;  7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  8  * };  9  */  10 class Solution {  11 public:  12     vector
     
      
        > pathSum(TreeNode *root, int sum) {  13           14         vector
       
        
          > gather;  15         vector
         
           rootLeaf;  16         int tempSum = 0;  17         pathSum(root, tempSum, sum, gather, rootLeaf);  18         return gather;  19     }  20       21     void pathSum(TreeNode *root, int tempSum, int sum, vector
          
           
             > &gather, vector
            
              rootLeaf) 22 { 23 if(root != NULL) 24 { 25 if(root->left == NULL && root->right == NULL) 26 { 27 tempSum += root->val; 28 rootLeaf.push_back(root->val); 29 if(tempSum == sum) 30 gather.push_back(rootLeaf); 31 32 return; 33 } 34 35 else 36 { 37 tempSum += root->val; 38 rootLeaf.push_back(root->val); 39 pathSum(root->left, tempSum, sum, gather, rootLeaf); 40 pathSum(root->right, tempSum, sum, gather, rootLeaf); 41 } 42 } 43 } 44 };