电子商务网站建设与管理案例,呼和浩特做网站,兰州市做网站的公司,免费搭建网站因为题目要求路径是从上到下的#xff0c;所以最好采用前序遍历。这样可以保证按从上到下的顺序将节点的值存入一个路径数组中。另外#xff0c;此题还有一个难点就是如何求得所有路径。为了解决这个问题#xff0c;我们需要用到回溯。回溯和递归不分家#xff0c;每递归一…因为题目要求路径是从上到下的所以最好采用前序遍历。这样可以保证按从上到下的顺序将节点的值存入一个路径数组中。另外此题还有一个难点就是如何求得所有路径。为了解决这个问题我们需要用到回溯。回溯和递归不分家每递归一次我们就回溯一次这样就能保证回到原来的位置进而递归我们没有走过的节点得到新的路径。大体思路就是这样大家可以结合我的代码以及注释理解这道题目。另外如果大家的二叉树遍历还不熟悉的话最好先去看一下我的关于二叉树遍历的博客再来看这道题否则肯定会比较懵逼。
代码及注释如下
/*** 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,vectorint path,vectorstring 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(); // 回溯}}vectorstring binaryTreePaths(TreeNode* root) {vectorint path;vectorstring result;if(root NULL) return result;travel(root,path,result);return result;}
};
