## Saturday, December 29, 2012

### [LeetCode] 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]
]
```
» Solve this problem

[解题报告]

[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:    }
``````