输入: root = {5,4,8,11,#,13,4,7,2,#,#,5,1}, sum = 22
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
输出: [[5,4,11,2],[5,8,4,5]]
解释:
两条路径之和为 22：
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
输入: root = {10,6,7,5,2,1,8,#,9}, sum = 18
10
/ \
6 7
/ \ / \
5 2 1 8
\
9
输出: [[10,6,2],[10,7,1]]
解释:
两条路径之和为 18：
10 + 6 + 2 = 18
10 + 7 + 1 = 18
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: a binary tree
* @param sum: the sum
* @return: the scheme
*/
vector<vector<int>> pathSum(TreeNode * root, int sum) {
// Write your code here.
vector<int> path;
vector<vector<int>> Spath;
int weight = 0;
findpath(Spath,root,sum,path,weight);
return Spath;
}
void findpath(vector<vector<int>> &Spath,TreeNode* root,int sum,vector<int> &path,int weight)
{
if(root == NULL){
return;
}
weight = weight + root->val;
path.push_back(root->val);
if(weight == sum && root->left == NULL && root->right == NULL)
{
Spath.push_back(path);
weight = weight - root->val;
path.pop_back();
return;
}
findpath(Spath,root->left,sum,path,weight);
findpath(Spath,root->right,sum,path,weight);
path.pop_back();
}
};
