Binary Tree Paths - 二叉树路径

• 题目：
  Given a binary tree, return all root-to-leaf paths.
  返回所有从根节点到叶子界面的路径

• 分析：

  1. 采用DFS的思想进行递归
  2. vector也同样具有栈的特性，所以使用vector来保存每一次遍历的节点，在适当位置弹出，造成vector复用
  3. 专门构造一个函数用于将vector中的节点和箭头拼接起来

• 代码：

vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        BFS (root, result, path);
        return result;
    }
    
    void BFS (TreeNode *treeNode, vector<string> &result, vector<int> &path) {
        if (treeNode == NULL) {
            return;
        }
        path.push_back(treeNode->val);
        if (treeNode->left == NULL && treeNode->right == NULL) {
            result.push_back(generatePath(path));
        }
        if (treeNode->left != NULL) {
            BFS (treeNode->left, result, path);
            path.pop_back(); // 这里对path进行弹栈，导致path复用，思路真是精妙
        }
        if (treeNode->right != NULL) {
            BFS (treeNode->right, result, path);
            path.pop_back();
        }
    }
    
    string generatePath(vector<int> path) {
        stringstream ss;
        int i;
        for (i = 0; i < path.size() - 1; i++) ss << path[i] << "->";
        ss << path[i];
        return ss.str();
    }