【树】113. 路径总和 II

 1 /**
 2  * Definition for a binary tree node.
 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     {
14         vector<vector<int> > rst;
15         vector<int> ivec;
16 
17         findSub(root, sum, rst, ivec);
18 
19         return rst;
20     }
21     
22 　　void findSub(TreeNode *root, int sum, vector<vector<int> > &vvec, vector<int> &ivec)
23     {
24         if(root == NULL)
25         {
26             return;
27         }
28 
29         ivec.push_back(root->val);
30 
31         if(!root->left && !root->right && root->val == sum)
32         {
33             vvec.push_back(ivec);
34 
35             ivec.pop_back(); //此刻的删除是：当前路径满足sum，那么则删除最后一个结点，然后回溯，访问其右孩子所在的那条路径或者是上一层的其他路径
36 
37             return;
38         }
39 
40         if(root->left)
41         {
42             findSub(root->left, sum - root->val, vvec, ivec);
43         }
44 
45         if(root->right)
46         {
47             findSub(root->right, sum - root->val, vvec, ivec);
48         }
49         
50         ivec.pop_back();            //此刻的删除是：当前的路径不满足sum，则删除最后一个节点，用于回溯，访问器右孩子的那条路径或者上一层的其他路径
51     }
52 };