【leetcode】Path Sum II

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.

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<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 };