Binary Tree Path

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

For example, given the following binary tree:

  1.    1
  2.  /   \
  3. 2     3
  4.  \
  5.   5

All root-to-leaf paths are:

  1. ["1->2->5", "1->3"]

题目翻译：
给定一棵二叉树，返回所有从根节点到叶节点的路径。

题目分析：
本题属于二叉树的遍历问题，可以用深度优先搜索来解决。

使用栈来记录遍历过程中访问过的节点。递归地访问每个节点的子节点，如果遇到叶节点，则输出记录的路径。返回上一层之前弹出栈顶元素。
C++的vector容器也能做到后进先出，所以下面的代码并没有使用std::stack类来实现。

生成输出的字符串时，可以使用std::stringstream类来完成，类似于Java和C#中的StringBuilder。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     vector<string> binaryTreePaths(TreeNode* root) {
  13.         vector<string> result;
  14.         if (root == nullptr) return result;
  15.         vector<int> path;
  16.         bfs(root, path, result);
  17.         return result;
  18.     }
  20. private:
  21.     // 递归函数，深度优先搜索
  22.     void bfs(TreeNode* node, vector<int>& path, vector<string>& result) {
  23.         if (node == nullptr) return;
  24.         path.push_back(node->val);
  25.         if (node->left == nullptr && node->right == nullptr)
  26.             result.push_back(generatePath(path));
  27.         else {
  28.             if (node->left != nullptr) {
  29.                 bfs(node->left, path, result);
  30.                 path.pop_back();
  31.             }
  32.             if (node->right != nullptr) {
  33.                 bfs(node->right, path, result);
  34.                 path.pop_back();
  35.             }
  36.         }
  37.     }
  39.     // 辅助函数，用于生成路径字符串
  40.     string generatePath(vector<int> path) {
  41.         stringstream ss;
  42.         int i;
  43.         for (i = 0; i < path.size() - 1; i++) ss << path[i] << "->";
  44.         ss << path[i];
  45.         return ss.str();
  46.     }
  47. };