# Binary Tree Path

> Given a binary tree, return all root-to-leaf paths.

> For example, given the following binary tree:
```
1
/ \
2 3
\
5
```
> All root-to-leaf paths are:
```
["1->2->5", "1->3"]
```

C++的vector容器也能做到后进先出，所以下面的代码并没有使用std::stack类来实现。

```c++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector binaryTreePaths(TreeNode* root) {
vector result;
if (root == nullptr) return result;
vector path;
bfs(root, path, result);
return result;
}

private:
// 递归函数，深度优先搜索
void bfs(TreeNode* node, vector& path, vector& result) {
if (node == nullptr) return;
path.push_back(node->val);
if (node->left == nullptr && node->right == nullptr)
result.push_back(generatePath(path));
else {
if (node->left != nullptr) {
bfs(node->left, path, result);
path.pop_back();
}
if (node->right != nullptr) {
bfs(node->right, path, result);
path.pop_back();
}
}
}

// 辅助函数，用于生成路径字符串
string generatePath(vector path) {
stringstream ss;
int i;
for (i = 0; i < path.size() - 1; i++) ss << path[i] << "->";
ss << path[i];
return ss.str();
}
};
```