文章目录
(完结2.2)
处理二叉树的解题思路
什么是递归?
递归就是深度优先遍历
递归的解题思路
1.确定参数和返回值,可以定义全局遍历,或者传入容器的引用
2.确定终止条件
3.确定单层递归逻辑
1.leetcode 144二叉树的前序遍历
Problem: 144. 二叉树的前序遍历
解题方法
1.参数的确立?
传如根节点,所以TreeNode *cur,同时遍历之后的结果存储到一个数组中,所以传入数组的引用
2.递归的终止条件?
就是cur为空代表当前节点没有,可以终止
3.单层逻辑
前序遍历,第一个节点就是根节点,直接push到容器中,第二个节点就是递归调用左子树,然后是递归调用右子树
复杂度
时间复杂度:
在 firstRoot 函数中,每个节点都会被访问一次,所以时间复杂度是 O(N),其中 N 是树中节点的数量。
preorderTraversal 函数只是调用了 firstRoot 函数,所以其时间复杂度也是 O(N)。
空间复杂度:
在递归过程中,每次递归调用都会使用一个栈帧,栈帧中包含了函数的局部变量和参数。在 firstRoot 函数中,递归调用了两次,所以最多会有两个栈帧同时存在。
在最坏情况下,树是一个链状结构,深度为 N。因此,递归调用的栈帧最多达到 N 个,因此空间复杂度是 O(N)。
此外,还需要额外的空间来存储结果,即 res 数组,它的大小与树中节点的数量成正比,所以空间复杂度也是 O(N)。
Code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void firstRoot(TreeNode *cur,vector<int> &res){
// 终止条件
if(cur==nullptr) return;
res.push_back(cur->val);
firstRoot(cur->left,res);
firstRoot(cur->right,res);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
firstRoot(root,result);
return result;
}
};
2.leetcode 145 二叉树的后序遍历
Problem: 145. 二叉树的后序遍历
解题方法
描述你的解题方法
复杂度
时间复杂度:
O ( n ) O(n) O(n)
空间复杂度:
O ( n ) O(n) O(n)
Code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> res;
void backFor(TreeNode *cur){
if(cur==nullptr) return;
backFor(cur->left);
backFor(cur->right);
res.push_back(cur->val);
}
vector<int> postorderTraversal(TreeNode* root) {
backFor(root);
return res;
}
};
3.leetcode 94 二叉树的中序遍历
Problem: 94. 二叉树的中序遍历
复杂度
时间复杂度:
O ( n ) O(n) O(n)
空间复杂度:
O ( n ) O(n) O(n)
Code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void mindiumFor(vector<int> &res,TreeNode *cur){
if(cur==nullptr) return;
mindiumFor(res,cur->left);
res.push_back(cur->val);
mindiumFor(res,cur->right);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
mindiumFor(res,root);
return res;
}
};