1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
public:
    void MoveOnPath(TreeNode *node,int sum,int &val,vector<int>&item,vector<vector<int>>&ans) {
        if(node == NULL) return;
        if(node->left == NULL && node->right == NULL) {
            if(sum == val) ans.push_back(item);
            return;
        }
        if(node->left != NULL) {
            val += node->left->val;
            item.push_back(node->left->val);
            MoveOnPath(node->left, sum, val, item, ans);
            val -= node->left->val;
            item.pop_back();
        }
        if(node->right != NULL) {
            val += node->right->val;
            item.push_back(node->right->val);
            MoveOnPath(node->right, sum, val, item, ans);
            val -= node->right->val;
            item.pop_back();
        }
    }
    vector<vector<int>> pathSum(TreeNode *root, int sum) {
        vector<vector<int>> ans;
        ans.clear();
        if(root == NULL) return ans;
        int val = 0;
        vector<int> item;
        item.clear();
        val += root->val;
        item.push_back(root->val);
        MoveOnPath(root, sum, val, item, ans);
        return ans;
    }
};