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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
unordered_map<TreeNode*,int> m;
unordered_map<TreeNode*,vector<int>> p;
vector<vector<int>> result;
queue<TreeNode*> que;
if(root != nullptr)
{
que.push(root);
m[root] = root->val;
p[root].push_back(root->val);
if(root->val == targetSum && root->left == nullptr && root->right == nullptr)
result.push_back(p[root]);
}
while(!que.empty())
{
int size = que.size();
for(int i = 0; i < size; i++)
{
TreeNode* node = que.front();
que.pop();
if(node->left)
{
m[node->left] = m[node] + node->left->val;
que.push(node->left);
p[node->left].insert(p[node->left].end(),p[node].begin(),p[node].end());
p[node->left].push_back(node->left->val);
if(m[node->left] == targetSum && node->left->left == nullptr && node->left->right == nullptr)
result.push_back(p[node->left]);
}
if(node->right)
{
m[node->right] = m[node] + node->right->val;
que.push(node->right);
p[node->right].insert(p[node->right].end(),p[node].begin(),p[node].end());
p[node->right].push_back(node->right->val);
if(m[node->right] == targetSum && node->right->left == nullptr && node->right->right == nullptr)
result.push_back(p[node->right]);
}
}
}
return result;
}
};
|