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