# Sharing my 16ms C++ non-recursive solution

• ``````vector<vector<int> > pathSum(TreeNode* root, int sum)
{
vector<vector<int>> ret;
vector<int> path;

if(!root)
return ret;

int left_visited = 0;//0: not visited; 1: visited
int right_visited = 0;
TreeNode* cur = root;
TreeNode* pre = NULL;
stack<TreeNode*> s;
s.push(cur);

while(!s.empty())
{
cur = s.top();
//计算当前结点的左右孩子是否被访问
if((pre && pre == cur->left) || (pre == cur && cur->left == NULL))
left_visited = 1;
else
left_visited = 0;
if((pre && pre == cur->right) || (pre == cur && cur->right == NULL))
right_visited = 1;
else
right_visited = 0;

//只有当结点的左右孩子都没有访问过时，才加入路径中
if(!left_visited && !right_visited)
path.push_back(cur->val);

//找到叶子结点，计算路径和，如果与sum相等，将该路径添加到ret
if(!cur->left && !cur->right)
{
int calc = accumulate(path.begin(), path.end(), 0);
if(calc == sum)
ret.push_back(path);
path.pop_back();
s.pop();
}
else//若不是，分类讨论
{
//如果右孩子已经被访问过，则应该执行回溯了，因为使用了前序遍历的逻辑
if(right_visited == 1)
{
path.pop_back();
s.pop();
}
else//如果没有，应该先判断左孩子是否访问；先访问左孩子
{
if(left_visited == 0 && cur->left != NULL)
s.push(cur->left);
else if(cur->right != NULL)
s.push(cur->right);
}
}
pre = cur;
}
return ret;
}
``````

代码解析见文章 Here is the analysis。使用了回溯法的思路，i consider it as a tracing-back problem

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