# Three 4ms c++ solutions given (recursion/ dfs stack based/ bfs queue based)

• (1)Recursion, if root is empty, return, if root is a leaf, then return cur+root->val, if root has childrens, then do recursion on each child, with cur updated to cur + root->val +"->"

``````class Solution {
void dfs(vector<string> &res, TreeNode *root, string cur)
{
if(!root->left && !root->right) res.push_back(cur  + std::to_string(root->val));
else
{
if(root->left) dfs(res, root->left,  cur  + std::to_string(root->val)+"->");
if(root->right) dfs(res, root->right, cur  + std::to_string(root->val)+"->");
}
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
if(root)  dfs(res, root, "");
return res;
}
};
``````

(2) DFS Version using a stack
Using a stack (the element is a pair of the current node pointer and the string recording the path from root to the current node). The logic is the same as (1)

``````class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
TreeNode *curNode;
string curPath;
stack<pair<TreeNode*, string>> liveNodes;
if(root) liveNodes.push(make_pair(root, ""));
while(!liveNodes.empty())
{
curNode = liveNodes.top().first;
curPath    = liveNodes.top().second;
liveNodes.pop();
if(!curNode->left && !curNode->right)
{
res.push_back(curPath + std::to_string(curNode->val));
}
else
{
if(curNode->left)  liveNodes.push(make_pair(curNode->left, curPath + std::to_string(curNode->val)+ "->"));
if(curNode->right) liveNodes.push(make_pair(curNode->right, curPath + std::to_string(curNode->val)+ "->"));
}
}
return res;
}
};
``````

(3) BFS queue based solution.
It prints all the paths in an ascending order of the path length

``````class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
queue<pair<TreeNode*, string>> liveNodes[2];
int cur=0, next=1;
TreeNode* curNode;
string curPath;
vector<string> res;

if(root) liveNodes[cur].push(make_pair(root, ""));
while(!liveNodes[cur].empty())
{
curNode = liveNodes[cur].front().first;
curPath = liveNodes[cur].front().second;
liveNodes[cur].pop();
if(!curNode->left && !curNode->right) res.push_back(curPath + std::to_string(curNode->val));
else{
if(curNode->left)  liveNodes[next].push(make_pair(curNode->left,  curPath + std::to_string(curNode->val) + "->"));
if(curNode->right) liveNodes[next].push(make_pair(curNode->right, curPath + std::to_string(curNode->val) + "->"));
}
if(liveNodes[cur].empty()) swap(cur, next);
}
return res;
}
};``````

• could you pls explain why not use reference-pass for para "cur" in function dfs, as :

void dfs(vector<string> &res, TreeNode *root, string & cur)

``````                                        /|\
``````

?

In fact, my idea is almost the same as yours, but I use the reference-pass and I can't pass all the test-case.

• If you use pass-by-reference, you have to recover cur everytime you return from a recursive call on a child node since cur will be changed in the recursive call. That is why I used pass-by-value since it guarantees that all the changes made in the recursive calls will not change cur in the current call.

• Thanks a lot for your explanation so clearly !!!

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