# C++ both recursive and iterative

• ``````class Solution {
public:
// iterative solution, post-order travel
vector<vector<int>> pathSum(TreeNode* root, int sum) {
stack<TreeNode*> st;
TreeNode* cur = root;
TreeNode* pre = NULL;
vector<int> path;
vector<vector<int>> ans;
int curSum = sum;
while(!st.empty() || cur != NULL){
if(cur != NULL){
st.push(cur);
path.push_back(cur->val);
curSum -= cur->val;
if(cur->left == NULL && cur->right == NULL && curSum == 0){
ans.push_back(path);
}
cur = cur->left;
}else{
TreeNode* top = st.top();
if(pre == top->right || top->right == NULL){
st.pop();
path.pop_back();
curSum += top->val;
pre = top;
}else{
cur = top->right;
}
}
}
return ans;
}
// recursive solution
/*
void backtrack(TreeNode* cur, vector<int>& path, int sum, vector<vector<int>>& ans){
if(cur == NULL){
return;
}
path.push_back(cur->val);
if(cur->left == NULL && cur->right == NULL){
if(sum == cur->val){
ans.push_back(path);
}
}
backtrack(cur->left, path, sum - cur->val, ans);
backtrack(cur->right, path, sum - cur->val, ans);
path.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> ans;
vector<int> path;
backtrack(root, path, sum, ans);
return ans;
}
*/
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.