257. 二叉树的所有路径

题目链接：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

我的想法：

        层次遍历不好解，可用找到叶子节点，但是他有一个回溯过程，他要一直保留路径节点，层次迭代不好加回溯。

        递归方法：

使用回溯三部曲：

        1.返回值无，入参多一个单个叶子节点的路径string和总共路径集合

void tranversal(TreeNode* cur, string path, vector<string>& result)

        2.停止条件

if (cur->left == NULL && cur->right == NULL) { // 遇到叶子节点
    string sPath;
    for (int i = 0; i < path.size() - 1; i++) { // 将path里记录的路径转为string格式
        sPath += to_string(path[i]);
        sPath += "->";
    }
    sPath += to_string(path[path.size() - 1]); // 记录最后一个节点（叶子节点）
    result.push_back(sPath); // 收集一个路径
    return;
}

        3.一层循环

if (cur->left) {
    traversal(cur->left, path, result);
    // 回溯
}
if (cur->right) {
    traversal(cur->right, path, result);
    // 回溯
}

代码：

//版本二
class Solution {
private:
    void traversal(TreeNode* cur, string path, vector<string>& result) {
        path += to_string(cur->val); // 中，中为什么写在这里，因为最后一个节点也要加入到path中
        if (cur->left == NULL && cur->right == NULL) {
            result.push_back(path);
            return;
        }
        if (cur->left) {
            path += "->";
            traversal(cur->left, path, result); // 左
            path.pop_back(); // 回溯 '>'
            path.pop_back(); // 回溯 '-'
        }
        if (cur->right) {
            path += "->";
            traversal(cur->right, path, result); // 右
            path.pop_back(); // 回溯'>'
            path.pop_back(); // 回溯 '-'
        }
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;

    }
};