二叉树的所有路径(力扣257)

因为题目要求路径是从上到下的，所以最好采用前序遍历。这样可以保证按从上到下的顺序将节点的值存入一个路径数组中。另外，此题还有一个难点就是如何求得所有路径。为了解决这个问题，我们需要用到回溯。回溯和递归不分家，每递归一次，我们就回溯一次，这样就能保证回到原来的位置，进而递归我们没有走过的节点，得到新的路径。大体思路就是这样，大家可以结合我的代码以及注释理解这道题目。另外，如果大家的二叉树遍历还不熟悉的话，最好先去看一下我的关于二叉树遍历的博客，再来看这道题，否则肯定会比较懵逼。

代码及注释如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
//参数有三个，一个为工作指针，一个为记录路径的数组，一个为储存最后结果的字符串数组
//注意千万不要将返回值设置为字符串数组，因为我们不需要每次递归都返回字符串，这跟之前每次递归返回数值不一样，我们这里将存储结果的容器放在参数引用就可以了
    void travel(TreeNode* cur,vector<int>& path,vector<string>& result){
        //这种记录路径的题目的递归终止条件不是遍历到空节点，而是遍历到叶子结点
        //为了确保将叶子结点也存入路径数组，需要在终止条件之前就push，否则会遗漏
        path.push_back(cur -> val);//处理逻辑
        //终止条件：遍历到叶子节点
         if(cur -> left == NULL && cur -> right == NULL){
            //将数字转化为题目所规定的字符串
            string spath;
            for(int i = 0;i < path.size() - 1;i++){
                spath += to_string(path[i]);
                spath += "->";
            }
            spath += to_string(path[path.size() - 1]);
            result.push_back(spath);
            return;
        }
         if (cur->left) { //递归左孩子 
            travel(cur->left, path, result);
            path.pop_back(); // 回溯
        }
        if (cur->right) { // 递归右孩子
            travel(cur->right, path, result);
            path.pop_back(); // 回溯
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
       vector<int> path;
       vector<string> result;
       if(root == NULL) return result;
       travel(root,path,result);
       return result;
 }
};