万网手机网站友情链接互换

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

代码及注释如下：

/*** 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;}
};