题目
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,
分析
本题目与上一题 LeetCode（112） Path Sum虽然类型相同，但是需要在以前的基础上，多做处理一些：
与Path Sum相比，本题是求出路径，所以，在找到满足的路径之后，不能直接返回，而是将其添加到一个vector < vector >中。在查找的过程中，每经过一个结点，先使用一个vector将该路径中的所有结点记录下来。由于vector< vector>是用来记录所有满足的路径的，所以传递引用给它是为了对它的每一个改动都是对其本身的操作，而不是对其副本的操作，使用来返回找到的所有路径。使用的vector只是拷贝操作，所以都是对其副本的操作，不会对原始的vector有影响。
AC代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if (!root)
return vector<vector<int>>();
//存储所有满足条件的路径
vector<vector<int> > paths;
//存储当前遍历路径
vector<int> tmp;
getPaths(root, sum, paths, tmp);
return paths;
}
void getPaths(TreeNode *root, int sum, vector<vector<int> > &paths, vector<int> tmp)
{
if (!root)
return;
tmp.push_back(root->val);
if (!root->left && !root->right && sum == root->val)
paths.push_back(tmp);
if (root->left)
getPaths(root->left, sum - root->val, paths, tmp);
if (root->right)
getPaths(root->right, sum - root->val, paths, tmp);
}
};