二叉树的所有路径：不仅递归，而且回溯给定一棵二叉树，返回从根节点到叶节点的所有路径。解释：叶节点是指没有子节点的节点。例子：思路本题需要从根节点到叶子的路径，所以需要先序遍历，方便父节点指向子节点，找到对应的路径。本题将首次涉及到回溯，因为我们需要记录路径，需要回溯才能回溯——一条路径进入另一条路径。前序遍历回溯的过程如图所示：我们先用递归的方法进行前序遍历。要知道递归和回溯是一家的，这道题也是需要回溯的。递归1、递归函数的函数参数和返回值要传递给根节点，记录每条路径的路径，并存储结果集的结果。这里，递归不需要返回值。代码如下：voidtraversal(TreeNode*cur,vector&path,vector&result)2.判断递归终止条件，然后写递归的时候，习惯这样写：if(cur==NULL){终止处理逻辑}但是这道题的终止条件写起来会很麻烦，因为这道题要找到叶子节点，就开始了end的处理逻辑（把路径放到result中）。那么叶子节点是什么时候找到的呢？当cur不为空且其左右子节点为空时，找到叶子节点。所以这道题的终止条件是：if(cur->left==NULL&&cur->right==NULL){终止处理逻辑}为什么没有判断cur是否为空，因为下面的逻辑可以控制空节点不进入循环。我们来看看终止处理的逻辑。这里使用vector结构体path来记录路径，所以必须将vector结构体的path转成string格式，再将string放入result中。那么为什么要用向量结构来记录路径呢？因为下面处理单层递归逻辑的时候，需要回溯，用vector回溯比较方便。可能有同学问过，我看到有些人的代码没有追溯。其实是有回溯的，只是隐藏在函数调用时的参数赋值中，后面会提到。这里我们首先使用vector结构的路径容器来记录路径，那么终止处理逻辑如下：if(cur->left==NULL&&cur->right==NULL){//leafnodestringsPath;for(inti=0;i";}sPath+=to_string(path[path.size()-1]);//记录最后一个节点（叶子节点）result.push_back(sPath);//收集一条路径return;}3.确定单层递归逻辑，因为是一个前序遍历，需要先处理中间节点，中间节点就是我们要记录的路径上的节点，先放到路径中。path.push_back(cur->val);然后就是递归回溯的过程。上面说了，不判断cur是否为空，所以这里递归的时候，如果为空，则不会进行下一级递归。所以在递归前要加判断语句，下面要递归的节点是否为空，如下if(cur->left){traversal(cur->left,path,result);}if(cur->right){traversal(cur->right,path,result);}还没结束，递归结束，需要回溯，因为path不能一直增加节点，需要先删除节点再增加新节点。那么如何回溯，有的同学会这样写，如下：if(cur->left){traversal(cur->left,path,result);}if(cur->right){traversal(cur->right,路径,结果);}path.pop_back();这个回溯是个大问题。我们知道回溯和递归是一一对应的。有递归就一定有回溯。递归和回溯是分开的，一个在花括号内，一个在花括号外。所以回溯应该总是和递归一起。世界上最远的距离，是你在花括号里，我在花括号外！那么代码应该这样写：->right,path,result);path.pop_back();//backtracking}那么这道题的整体代码如下：classSolution{private:voidtraversal(TreeNode*cur,vector&path,vector&result){path.push_back(cur->val);//这是叶子节点if(cur->left==NULL&&cur->right==NULL){stringsPath;for(inti=0;i";}sPath+=to_string(path[path.size()-1]);result.push_back(sPath);返回;}if(cur->left){遍历(cur->left,path,result);path.pop_back();//回溯}if(cur->right){遍历(cur->right,path,result);path.pop_back();//回溯}}public:vectorbinaryTreePaths(TreeNode*root){vectorresult;vectorpath;if(root==NULL)returnresult;traversal(root,路径,结果);返回结果;}};上面的C++代码充分体现了回溯。那么上面的代码可以简化为如下代码：==NULL&&cur->right==NULL){result.push_back(path);return;}if(cur->left)traversal(cur->left,path+"->",result);//左if(cur->right)traversal(cur->right,path+"->",result);//right}public:vectorbinaryTreePaths(TreeNode*root){vectorresult;stringpath;if(root==NULL)returnresult;遍历(root,path,result);returnresult;}};上面的代码简化了很多，隐藏了很多东西。注意，函数定义时，voidtraversal(TreeNode*cur,stringpath,vector&result)定义的是stringpath，每次都复制赋值，不使用引用，否则无法实现回溯的效果。那么在上面的代码中，看似没有看到回溯逻辑，其实回溯是隐藏在traversal(cur->left,path+"->",result)中的path+"->";每次调用该函数，路径仍然没有加“->”，这是回溯。为了显示这段简化代码的回溯过程，可以试试：if(cur->left)traversal(cur->left,path+"->",result);//这里把左回溯隐藏改成以下代码：path+="->";traversal(cur->left,path,result);//左边是：if(cur->left){path+="->";traversal(cur->left,path,result);//left}if(cur->right){path+="->";traversal(cur->right,path,result);//right}此时没有回溯，这段代码了只是不会通过。如果要加回溯，需要在上面代码的基础上加回溯，可以AC。if(cur->left){path+="->";traversal(cur->left,path,result);//左路径.pop_back();//回溯路径.pop_back();}if(cur->right){path+="->";traversal(cur->right,path,result);//rightpath.pop_back();//回溯path.pop_back();}大家应该能感觉到，如果把路径+“->”作为函数参数就可以了，因为路径的值并没有改变。递归函数执行完后，路径还是之前的值（相当于回溯）。基于以上，第二个递归代码虽然精简了但是在代码细节上隐藏了很多重要的地方。第一种递归的写法虽然代码较多，但是把每一个逻辑处理都展现的淋漓尽致。迭代法对于非递归的方法，我们仍然可以使用前序遍历的迭代法来模拟遍历路径的过程。不懂迭代法的同学可以看看二叉树一文：听说递归可以做，栈也可以做！和BinaryTree：前中后序迭代的统一写法。这里除了模拟递归，还需要一个栈，还需要一个栈来存放对应的遍历路径。C++代码如下：classSolution{public:vectorbinaryTreePaths(TreeNode*root){stacktreeSt;//保存树遍历节点stackpathSt;//保存遍历路径节点向量result;//保存最终路径集合if(root==NULL)returnresult;treeSt.push(root);pathSt.push(to_string(root->val));while(!treeSt.empty()){TreeNode*node=treeSt.top();treeSt.pop();//取出节点字符串path=pathSt.top();pathSt.pop();//取出节点对应的路径if(node->left==NULL&&node->right==NULL){//遇到一个叶节点result.push_back(path);}if(node->right){//righttreeSt.push(node->right);pathSt.push(path+"->"+to_string(node->right->val));}if(node->left){//lefttreeSt.push(node->left);pathSt.push(path+"->"+to_string(node->left->val));}}returnresult;}};当然，使用java的同学可以直接定义一个栈，其成员变量为objectStackstack=newStack<>();，这样就不用定义两个栈了，都放在一个栈里就行了。总结这篇文章，我们最初涉及到回溯。很多过了这个题目的同学可能不知道其实用的是回溯。回溯和递归是相辅相成的。在第一版递归代码中，我充分展示了递归和回溯的细节，大家可以自己感受一下。第二版的递归代码其实对初学者很不友好。代码看似简单，但细节却隐藏在无形之中。最后还是给了迭代的方法。在充分理解了递归和局部回溯的过程后，精力充沛的同学就可以实现迭代法了。其他语言版本Java：//解法一类解决方案{/***递归法*/publicListbinaryTreePaths(TreeNoderoot){Listres=newArrayList<>();if(root==null){returnres;}Listpaths=newArrayList<>();traversal(root,paths,res);returnres;}privatevoidtraversal(TreeNoderoot,Listpaths,Listres){paths.add(root.val);//叶子结点if(root.left==null&&root.right==null){//输出StringBuildersb=newStringBuilder();for(inti=0;i");}sb.append(paths.get(paths.size()-1));res.add(sb.toString());返回;}if(root.left!=null){traversal(root.left,paths,res);paths.remove(paths.size()-1);//回源}if(root.right!=null){遍历(root.right,paths,res);paths.remove(paths.size()-1);//回源}}}Python：classSolution:defbinaryTreePaths(self,root:TreeNode)->List[str]:path=[]res=[]defbacktrace(root,path):ifnotroot:returnpath.append(root.val)if(notroot.left)and(notroot.right):res.ap挂起（路径[：]）方式=[]ifroot.left：ways.append（root.left）ifroot.right：ways.append（root.right）forwayinways：回溯（方式，路径）path.pop（）回溯（root,path)return["->".join(list(map(str,i)))foriinres]Go：funcbinaryTreePaths(root*TreeNode)[]string{res:=make([]string,0)vartravelfunc(节点*TreeNode,sstring)travel=func(node*TreeNode,sstring){ifnode.Left==nil&&node.Right==nil{v:=s+strconv.Itoa(node.Val)res=append(res,v)return}s=s+strconv.Itoa(node.Val)+"->"ifnode.Left!=nil{travel(node.Left,s)}ifnode.Right!=nil{travel(node.Right,s)}}旅行（根，“”）returnres}
