Recommended: Solve Path Sum before viewing the solution below.
Approach 1
This can be solved using a very similar code written in Path Sum. We just need to return a 2D vector of paths which sum up to given sum in the recursion. If we deal with vectors, we’ll have to make some adjustments for returning such path. I’ll explain it after the code below.
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if (root==NULL)
return {};
if (!root->left && !root->right && root->val==sum) return ;
vector<vector<int>> left = pathSum(root->left, sum-root->val);
vector<vector<int>> right = pathSum(root->right, sum-root->val);
vector<vector<int>> res;
for (int i=0; i<left.size(); i++) {
reverse(left[i].begin(), left[i].end());
left[i].push_back(root->val);
reverse(left[i].begin(), left[i].end());
res.push_back(left[i]);
}
for (int i=0; i<right.size(); i++) {
reverse(right[i].begin(), right[i].end());
right[i].push_back(root->val);
reverse(right[i].begin(), right[i].end());
res.push_back(right[i]);
}
return res;
}
The adjustment we are making is that we are reversing the path, then pushing the current element and then reversing it again. See the explanation below:
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
Imagine we are at node 4. The left variable will be equal to 11 and the right variable will be an empty vector {}. Now, we want to return the path 4. How do we push 4 to the left path? The only way is to reverse it (making it {2, 11}) and then pushing 4 (making it {2, 11, 4}) and then reversing it again ({4, 11, 2}).
Approach 2
This approach is just a small tweak in the previous approach so please understand approach 1 first.
Linked Lists give us the functionality of pushing an element to the starting of the list in constant time. This is the functionality which is lacking from vectors and the reason why we have to make the reverse adjustments in the previous approach. The code below uses linked lists instead to store the paths and then parses it to return a 2D vector.
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if (root == NULL) return {};
vector<list<int>> v = helper(root, sum);
vector<vector<int>> res;
for (auto l : v) {
vector<int> t;
for (auto i : l)
t.push_back(i);
res.push_back(t);
}
return res;
}
vector<list<int>> helper(TreeNode* root, int sum) {
if (root==NULL)
return {};
if (root->left == NULL && root->right==NULL && root->val==sum) return ;
vector<list<int>> left = helper(root->left, sum-root->val);
vector<list<int>> right = helper(root->right, sum-root->val);
vector<list<int>> res;
for (int i=0; i<left.size(); i++) {
left[i].push_front(root->val);
res.push_back(left[i]);
}
for (int i=0; i<right.size(); i++) {
right[i].push_front(root->val);
res.push_back(right[i]);
}
return res;
}
};