Path Sum II (C++ code)

Leetcode Path Sum II, Oct 14 '122982 / 8423
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]
]

思路：递归。用完某个node之后记得把值pop出来。

0. void findpath(TreeNode *root, int sum, vector<vector<int>> &res, vector<int> &path){  
1.   
2.   if(!root->left && !root->right){  
3.   
4.        if(sum == 0) res.push_back(path);  
5.   
6.        return;   
7.   
8.   }   
9.   
10.   if(root->left){  
11.   
12.     path.push_back(root->left->val);   
13.   
14.     findpath(root->left, sum - root->left->val, res, path);  
15.   
16.     path.pop_back();   
17.   
18.   }  
19.   
20.   if(root->right){   
21.   
22.     path.push_back(root->right->val);  
23.   
24.     findpath(root->right, sum - root->right->val, res, path);  
25.   
26.     path.pop_back();  
27.   
28.   }  
29.   
30. }   
31.   
32.    
33.   
34. vector<vector<int> > pathSum(TreeNode *root, int sum) {  
35.         vector<vector<int>> res;  
36.   
37.         vector<int> path;   
38.   
39.         if(!root) return res;  
40.   
41.         path.push_back(root->val);  
42.   
43.         findpath(root, sum - root->val, res, path);  
44.         return res;  
45.     }