泪眼朦胧
V1
2022/02/07阅读:83主题:默认主题
递归怎么才能写对?
每次写递归都是碰运气写对,递归到底怎么写?
递归看似简单好理解,但是经常一写就错。
编写递归代码时,掌握这三部分,可以保证大家写出正确的递归算法。
-
确定递归函数的参数和返回值: 确定哪些参数是递归过程中需要处理的,需要处理的加在递归函数的参数上,并且还要确认递归函数的返回值以确认返回值的类型。 -
递归的终止条件: 避免忘记写递归函数的终止条件或者写错导致内存栈溢出。 -
单次递归需要完成的工作:确定单次递归需要做的事件,多层递归就把整件事情解决了。
这里以二叉树的前中后序遍历来尝试一下。
二叉树的前序遍历, 先遍历根节点,再遍历左子树节点,再遍历右子树节点。
-
确定递归函数的参数和返回值: 递归过程需要对一个vector 进行追加操作,追加节点的值,也就是前序遍历的结果,vector需要作为递归函数的参数,遍历的结果直接放进了vector,不需要返回值,所以递归函数返回值为void。
void Traversal(TreeNode *node, vector<int> &ans) {
} -
递归函数的终止条件: 当遍历节点为空时,递归结束了。
void Traversal(TreeNode *node, vector<int> &ans) {
if (node == nullptr) {
return;
}
} -
单层递归需要做的事: 前序遍历,中左右,所以单层递归时,先加入根节点的值,再递归左子节点,再递归右子节点。
void Traversal(TreeNode *node, vector<int> &ans) {
if (node == nullptr) {
return;
}
ans.push_back(root->val); // 先根
Traversal(node->left); // 左
Traversal(node->right); // 右
}
完整的代码像这样:
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
Traversal(root, ans);
return ans;
}
private:
void Traversal(TreeNode *root, vector<int> &ans) {
if (root == nullptr) {
return;
}
ans.push_back(root->val); // 先根
Traversal(root->left, ans); // 左
Traversal(root->right, ans); // 右
}
}
中序遍历,后序遍历也是同样的道理,快去试试吧。
作者介绍
泪眼朦胧
V1