?一看就知道，一写就废！?这次我们要说的是递归。是的，一写就废了。”主要是递归没有体系，没有方法论。“我每次写递归算法，都是靠玄学写代码。代码能不能编译通过就看运气了。”本文将介绍前中后序递归的写法。有的同学可能觉得很简单，其实不然。我们需要通过简单的主题来确定方法论。有了方法论，后面再处理复杂的递归就可以了。”这里帮大家确定递归算法的三要素。“每次写递归的时候，按照这三个要素来写，这样可以保证大家写出正确的递归算法!"在递归函数中加入这个参数，同时指定每次递归的返回值是什么，来确定递归函数的返回类型。"确定终止条件：经常会遇到栈溢出错误，就是没有写终止条件或者终止条件写错了，操作系统也是用栈结构来保存每一层递归的信息，如果递归没有终止，内存栈操作系统难免会溢出《判断单级递归逻辑：》判断ea需要处理的信息ch递归级别。这里，重复调用自己实现递归的过程也会重复。好了，我们确认了递归的三要素，接下来我们来练习一下：《下面是一个先序遍历的例子：》《确定递归函数的参数和返回值》：因为先序遍历节点的取值是被打印出来，参数需要传入vector中节点的值，除此点外不需要处理任何数据，也没有返回值，所以递归函数的返回类型为void，代码如下：voidtraversal(TreeNode*cur,vector&vec)《判断终止条件》：在递归的过程中，递归是如何结束的？当然，如果当前遍历的节点为空，那么这一层的递归就要结束了，所以如果当前遍历的节点为空，直接返回即可，代码如下：if(cur==NULL)return;《判断单级递归的逻辑》：前序遍历是中左右的顺序，所以单级递归的逻辑是先取中间节点的值，代码如下如下：vec.push_back(cur->val);//中间遍历(cur->left,vec);//左遍历(cur->right,vec);//右单层递归的逻辑按照至此左右序处理完毕，至此二叉树的前序遍历基本完成。先看完整代码：前序遍历：classSolution{public:voidtraversal(TreeNode*cur,vector&vec){if(cur==NULL)return;vec.push_back(cur->val);//中间遍历(cur->left,vec);//左遍历(cur->right,vec);//右}vectorpreorderTraversal(TreeNode*root){vectorresult;traversal(root,result);返回结果;}};前序遍历写完了，中序和后序遍历就不难理解了。代码如下：中序遍历：voidtraversal(TreeNode*cur,vector&vec){if(cur==NULL)return;traversal(cur->left,vec);//leftvec.push_back(cur->val);//中遍历(cur->right,vec);//右}后序遍历:voidtraversal(TreeNode*cur,vector&vec){if(cur==NULL)return;traversal(cur->left,vec);//向左遍历(cur->right,vec);//向右vec.push_back(cur->val);//中间}这时候可以做leetcode上的三题，分别是：144.二叉树的前序遍历145.二叉树的后序遍历94.二叉树的中序遍历可能有同学觉得前后中序遍历的递归太简单了，而应该用迭代法（非递归），别着急，明天我们就玩前中后序的迭代法一一说清楚！本文转载自微信公众号“代码随想录”，您可以通过以下二维码关注转载文章，请联系代码随想记录公众号。
