Path Sum II

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

              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<vector<int> > pathSum(TreeNode *root, int sum) {13         vector<int> tmp;14         vector<vector<int> > result;15         if(root==NULL)16         {17             return result;18         }19         DFS(root,sum,tmp,result);20         return result;21        22     }23    24     void DFS(TreeNode *root,int &sum, vector<int> tmp,vector<vector<int> > &result,int cur=0)25     {26         if(root==NULL)27         {28             return;29         }30  31         int val=root->val;32         tmp.push_back(val);33        34         if(root->left==NULL&&root->right==NULL)35         {36             if(cur+val==sum) result.push_back(tmp);37             return;38         }39         DFS(root->left,sum,tmp,result,cur+val);40         DFS(root->right,sum,tmp,result,cur+val);41     }42 };