递归函数什么时候返回值，什么时候不返回值？

相信很多同学都会疑惑递归函数什么时候有返回值，什么时候没有，尤其是递归函数的返回类型是bool的时候。那么我将通过详细解释以下两个问题来回答这个问题：112.路径总和113.路径总和ii112.路径和题地址：https://leetcode-cn.com/problems/path-sum/给定一棵二叉树和一个目标和，判断树中是否存在从根节点到叶子节点的路径，和这条路径上所有节点值的和等于目标总和。解释：叶节点是指没有子节点的节点。例子：给定如下二叉树，目标和=22，返回真，因为从目标和为22的根节点到叶子节点有一条路径5->4->11->2。思路对于这道题，我们需要遍历从根节点到叶子节点的路径，看看和是不是目标和。递归可以使用深度优先遍历的方法（这道题可以用前中后顺序，无所谓，因为中间节点没有处理逻辑）遍历二叉树确定参数并返回递归函数的类型参数：需要二叉树的根节点，还需要一个计数器，这个计数器用来计算二叉树某条边的和是否恰好是目标和，计数器为整数类型。我们再看看返回值。递归函数什么时候需要返回值？什么时候不需要返回值？这里有以下三点：如果需要查找整个二叉树，不需要对递归返回值进行处理，那么递归函数不应该有返回值。（这种情况是本文后半部分介绍的113.Pathsumii）如果需要查找整棵二叉树，需要对递归返回值进行处理，递归函数需要返回值。（在这种情况下，我们在236.二叉树的最近公共祖先中引入）如果要搜索其中一条符合条件的路径，那么递归必须返回一个值，因为遇到符合条件的路径必须及时返回小路。（本题情况）本题我们是在寻找一条满足条件的路径，所以递归函数需要有返回值，并且及时返回，那么返回类型是什么？如图：112.从路径和图中可以看出，遍历路由不需要遍历整棵树，所以递归函数需要返回一个值，可以用bool类型表示。所以代码如下：booltraversal(treenode*cur,intcount)//注意函数的返回类型决定了终止条件。首先，计数器如何统计这条路径的总和？不要先加起来再判断是否等于目标和，那代码比较麻烦，可以用Decrement，让计数器计数初始为目标和，然后每次减去遍历路径节点上的值时间。如果最后的count==0和叶子节点同时到达，就说明目标和已经找到了。如果遍历叶子节点，count不为0，则没有找到。递归终止条件代码如下：if(!cur->left&&!cur->right&&count==0)returntrue;//遇到叶子节点，计数为0if(!cur->left&&!cur->right)returnfalse;//遇到一个叶子节点但是没有找到合适的边，直接返回判断单级递归的逻辑。因为终止条件是判断叶子节点，所以在递归过程中不要让空节点进入递归。递归函数有一个返回值。如果递归函数返回真，则表示找到了合适的路径，应立即返回。代码如下：if(cur->left){//Left（不遍历空节点）//如果一个叶子节点返回true，则直接返回trueif(traversal(cur->left,count-cur->left->val))returntrue;//注意这里有回溯逻辑}if(cur->right){//right（空节点不遍历）//遇到叶子节点返回true，直接返回trueif(遍历(cur->right,count-cur->right->val))returntrue;//注意这里有回溯逻辑}returnfalse;以上代码包含回溯，不回溯，如何回溯，另寻路径。回溯隐藏在traversal(cur->left,count-cur->left->val)中，因为count-cur->left->val直接作为参数传入，函数结束，count的值没有改变。为了体现回溯的过程，可以改成如下代码：if(cur->left){//leftcount-=cur->left->val;//递归，处理节点；if(traversal(cur->left,count))returntrue;count+=cur->left->val;//回溯，撤销处理结果}if(cur->right){//rightcount-=cur->right->val;if(traversal(cur->right,count))returntrue;count+=cur->right->val;}returnfalse;整体代码如下：classsolution{private:booltraversal(treenode*cur,intcount){if(!cur->left&&!cur->right&&count==0)returntrue;//遇到叶子节点，计数为0if(!cur->left&&!cur->right)returnfalse;//遇到叶子节点node并直接返回if(cur->left){//Leftcount-=cur->left->val;//递归，处理节点；if(traversal(cur->left,count))returntrue;count+=cur->left->val;//回溯，撤销处理结果}if(cur->right){//rightcount-=cur->right->val;//递归，处理节点；if(traversal(cur->right,count))returntrue;count+=cur->right->val;//回溯，撤销处理结果}returnfalse;}public:boolhaspathsum(treenode*root,intsum){if(root==null)returnfalse;returntraversal(root,sum-root->val);}};上面的代码简化如下：classsolution{public:boolhaspathsum(treenode*root,intsum){if(root==null)returnfalse;if(!root->left&&!root->right&&sum==root->val){returntrue;}returnhaspathsum(root->left,sum-root->val)||haspathsum(root->right,sum-root->val);}};大家有没有发现精简后的代码已经完全失去了分析的过程，所以我们要把标题分析清楚之后，在追求代码精简的过程中强调过很多次了！如果迭代使用栈来模拟递归，那如果我们做回溯呢？这时候，栈中的一个元素不仅要记录节点指针，还要记录节点从一开始到这个节点的路径值之和。在c++中，我们使用pair结构来存储这个栈中的元素。定义为：pair这是栈中的一个元素。下面的代码是使用栈模拟的前序遍历，如下：（详细注释）classsolution{public:boolhaspathsum(treenode*root,intsum){if(root==null)returnfalse;//此时pair为被放入栈stack>st;st.push(pair(root,root->val));while(!st.empty()){pairnode=st.top();st.pop();//如果该节点是叶节点且该节点的路径值等于sum，则返回trueif(!node.first->left&&!node.first->right&&sum==node.second)returntrue;//右节点，当按下一个节点时，记录该节点的路径值if(node.first->right){英石。push(pair(node.first->right,node.second+node.first->right->val));}//左节点，当按下一个节点时，该节点的路径值为还记录了if(node.first->left){st.push(pair(node.first->left,node.second+node.first->left->val));}}返回假；}}；如果完全理解局部递归方法，可以顺便做leetcode上的113.路径求和ii。113.路径和ii题目地址：https://leetcode-cn.com/problems/path-sum-ii/给定一棵二叉树和一个目标和，求从根节点到叶子节点的所有路径之和相等到给定的目标和路径。解释：叶节点是指没有子节点的节点。例子：给定如下二叉树，并且target和sum=22，idea113。路径sumii需要遍历整棵树找到所有路径，所以递归函数没有返回值！如图：113.pathsumii尽可能详细的体现出来，我写了下面的代码（这段代码不简洁，但是逻辑很清晰）classsolution{private:vector>result;vectorpath;//递归函数不需要返回值，因为我们要遍历整棵树voidtraversal(treenode*cur,intcount){if(!cur->left&&!cur->right&&count==0){//遇到了一个叶子节点，找到了一条路径和sumresult.push_back(path);return;}if(!cur->left&&!cur->right)return;//遇到了一个叶子节点但是没有找到合适的边，直接返回if(cur->left){//Left（空节点不遍历）path.push_back(cur->left->val);count-=cur->left->val;traversal(cur->left,count);//递归count+=cur->left->val;//回溯path.pop_back();//回溯}if(cur->right){//right(空节点不遍历)path.push_back(cur->right->val);count-=cur->right->val;traversal(cur->right,count);//递归count+=cur->right->瓦尔;//回溯path.pop_back();//回溯}return;}public:vector>pathsum(treenode*root,intsum){result.clear();path.clear();if(root==null)returnresult;path.push_back(root->val);//将根节点放入路径遍历(root,sum-root->val);returnresult;}};至于113.路径sumii的迭代方法我没写，记录一下迭代所有的路径比较麻烦，也没有必要。有兴趣的可以通过leetcode112.Pathsum113.Pathsumii进一步研究和总结这篇文章，详细解释了递归函数什么时候需要返回值，什么时候不需要返回值。这两道题都是很好掌握这个知识点的题。看完这篇文章再做题，你会感受到搜索整棵树和搜索某条路径的区别。对于112.路径求和，我还是给出了递归的方法和迭代的方法。其实这种题目迭代法比较复杂，掌握递归法就够了！按照下面的二维码进行操作。转载本文请联系CodeCaprice公众号。