For example:
Given the below binary tree and
sum = 22
,5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[» Solve this problem
[5,4,11,2],
[5,8,4,5]
]
[解题报告]
二叉树递归。
[Code]
1: vector<vector<int> > pathSum(TreeNode *root, int sum) {
2: // Start typing your C/C++ solution below
3: // DO NOT write int main() function
4: vector<vector<int> > collect;
5: vector<int> solution;
6: if(root!=NULL)
7: GetPath(root, sum, 0, solution, collect);
8: return collect;
9: }
10: void GetPath(TreeNode* node, int sum, int cal, vector<int>& solution, vector<vector<int> >& collect)
11: {
12: solution.push_back(node->val);
13: cal += node->val;
14: if(cal == sum && node->left == NULL && node->right == NULL)
15: {
16: collect.push_back(solution);
17: }
18: else
19: {
20: if(node->left != NULL)
21: {
22: GetPath(node->left, sum, cal, solution, collect);
23: }
24: if(node->right != NULL)
25: {
26: GetPath(node->right, sum, cal, solution, collect);
27: }
28: }
29: solution.pop_back();
30: cal -= node->val;
31: return;
32: }