# C++ iterative solution with one vector, 17ms

• Basically use a vector as a stack and do a standard in-order traversal. The reason to use vector is for easily backtracking. Instead of popping out a node from the stack before traversing its right child, I kept it in the "stack" with a mark so as to track the whole path.

class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> paths;
if (!root) return paths;
// vector element: {current node, {remainder from root till current node, mark whether this node has been visited}}
vector<pair<TreeNode *, pair<int, int>>> st;
TreeNode * cur = root;
int rs = sum;
while (cur) {
rs -= cur->val;
st.push_back({cur, {rs, 0}});
cur = cur->left;
}
while (!st.empty()) {
auto& e = st.back();
if (e.second.second == 1) {
st.pop_back();
continue;
} else {
e.second.second = 1;
}
if (e.second.first == 0 && !e.first->left && !e.first->right) {
vector<int> inst;
for (auto it = st.begin(); it != st.end(); it++) inst.push_back(it->first->val);
paths.push_back(inst);
}
cur = e.first->right;
rs = e.second.first;
while (cur) {
rs -= cur->val;
st.push_back({cur, {rs, 0}});
cur = cur->left;
}
}
return paths;
}
};

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