【算法套路】-【递归篇】
文章目录
【算法套路】-【递归篇】前言递归三要素前言
本文参考·【代码随想录】·大佬的二叉树:一入递归深似海,从此offer是路人,希望在写递归脑子糊涂的时候,给自己一点灵光。
递归三要素
三要素其实就是递归的模板,按照三要素来写递归就是递归的套路。
1、确定递归函数的参数和返回值
:确定递归过程中需要处理的参数,明确每次递归的返回值进而确定递归函数的返回类型
2、确定递归终止条件
,即函数return的出口:终止条件写的不对,操作系统的内存栈一定会溢出,毕竟递归也是有限制的
3、确定单层递归的逻辑
:明确每次递归要进行什么操作
以二叉树的前序遍历为例:
class Solution {public:void traversal(TreeNode* cur, vector<int>& vec) {//1:函数参数&返回值if (cur == NULL) return; //2:终止条件vec.push_back(cur->val); // 中 //3开始:单层递归逻辑traversal(cur->left, vec); // 左traversal(cur->right, vec); // 右//3结束}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}};
具体题目中使用到递归时,很少能够直接使用本函数进行递归:preorderTraversal()
函数作为执行的主体函数,并不进行递归,而是将递归函数traversal()
写在外部。
因为前序遍历访问顺序是根-左-右
,单层逻辑就是顺序访问根-左-右
的节点,因此需要为形参cur
传入实参root
,并将节点值保存在vector中。递归的终止条件是当前节点为空时返回上一级节点,这种写法也是二叉树的遍历中最常用的一种写法。