题目链接：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] 
]

这道题的要求是找出二叉树中从根节点到叶子节点的路径之和等于给定sum的所有路径。

继承Path Sum。同样采用递归思路，如果当前节点为NULL，返回；如果当前节点的左右子树均为NULL，而且val等于sum，记录该情形；剩下情况，用sum减去val，然后递归处理左右子树。

时间复杂度：O(n)

空间复杂度：O(1)

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

class Solution
{
    vector<vector<int> > vvi;
public:
    vector<vector<int> > pathSum(TreeNode *root, int sum)
    {
        vector<int> vi;
        pathSum(root, sum, vi);
        return vvi;
    }
private:
    void pathSum(TreeNode *p, int sum, vector<int> &vi)
    {
        if(p == NULL)
            return;
        
        vi.push_back(p -> val);
        if(p -> left == NULL && p -> right == NULL)
            if(p -> val == sum)
                vvi.push_back(vi);
        if(p -> left != NULL)
            pathSum(p -> left, sum - p -> val, vi);
        if(p -> right != NULL)
            pathSum(p -> right, sum - p -> val, vi);
        vi.pop_back();
    }
};