代码随想录算法训练营第14天 | 144.二叉树的前序遍历、145.二叉树的后序遍历、94.二叉树的中序遍历
144. 二叉树的前序遍历 - 力扣（LeetCode）
因为这三道题目比较类似，所以思路都放在一起讲
递归写法
递归写法要注意理解递归这一过程，写递归主要确定三步
确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
——引用自代码随想录
在遍历的时候，需要二叉树节点来遍历整个二叉树，还需要一个数组来储存结果，所以传入TreeNode*和vector<int>&，每次进递归循环的时候先判断节点是否为空，这是循环的终止条件。然后再根据遍历的类型确定每个节点的先后顺序，如此循环反复就可以得到结果了。
迭代写法
前序遍历
迭代写法的思路主要是利用栈来模拟递归的过程，因为实际上递归就是系统用栈来完成的。我们从root出发，每次先把root的值放入ans数组中，然后再看node->right和node->left是否为空，非空则推入栈中。具体的算法过程看代码就可以看明白，用语言描述可能会比代码复杂很多，这里主要强调要注意的点，因为是把数据推入栈中，出栈的原则是先进后出，所以为了保证顺序是中左右，我们得先把node->right推入栈，接着再把node->left推入栈。
中序遍历
中序遍历的思路其实和前序遍历很不一样，因为前序遍历可以由中间值去找左右，但中序遍历很难由左右去找中间值。元素访问顺序和处理顺序是不一致的，具体实现还是看代码。
后序遍历
因为前序输出的结果是中左右，而后序要求的是左右中，只要我们改变前序输出时node->right和node->left进栈的顺序，即这两行代码交换，就可以让输出结果变成中右左，此时再翻转一下结果数组，我们就得到了左右中
统一迭代法
统一迭代法的思想是无论该元素是否需要处理，都一律放入栈中，但是会在要处理的元素后面后加入一个空指针来做标记。我们按照要求遍历数组，如果栈顶指针非空，我们就先弹出栈顶数据，根据前中后序(看是哪一道题)的反向顺序处理数据，依此再推入栈中，轮到推入当前指针时，应在后面加入一个空指针。如果栈顶指针为空，就弹出该指针，然后将此时的栈顶数据(空指针弹出后)存入结果数组，循环结束得到的结果数组中存的就是答案。
使用统一迭代法写前中后序的话代码风格比较统一，在前中后序三种方式中来回切换只需要改变部分代码的顺序即可，十分方便，我更喜欢这种迭代方式
我的AC代码
递归写法
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
void traversal(TreeNode* t, vector<int>& ans) {
if(t == nullptr) {
return;
}
ans.push_back(t->val);
traversal(t->left, ans);
traversal(t->right, ans);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
traversal(root, ans);
return ans;
}
};迭代写法
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> ans;
if(root == nullptr) {
return ans;
}
st.push(root);
while(!st.empty()) {
TreeNode* node = st.top();
ans.push_back(node->val);
st.pop();
if(node->right != nullptr) {
st.push(node->right);
}
if(node->left != nullptr) {
st.push(node->left);
}
}
return ans;
}
};统一迭代写法
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> ans;
if(root == nullptr) {
return ans;
}
st.push(root);
while(!st.empty()) {
TreeNode* node = st.top();
if(node != nullptr) {
TreeNode* tmp = node;
st.pop();
if(tmp->right) {
st.push(tmp->right);
}
if(tmp->left) {
st.push(tmp->left);
}
st.push(tmp);
st.push(nullptr);
}
else {
st.pop();
TreeNode* tmp = st.top();
st.pop();
ans.push_back(tmp->val);
}
}
return ans;
}
};94. 二叉树的中序遍历 - 力扣（LeetCode）
我的AC代码
递归写法
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
void traversal(TreeNode* t, vector<int>& ans) {
if(t == nullptr) {
return;
}
traversal(t->left, ans);
ans.push_back(t->val);
traversal(t->right, ans);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
traversal(root, ans);
return ans;
}
};迭代写法
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
TreeNode* node = root;
stack<TreeNode*> st;
if(node == nullptr) {
return ans;
}
while(node != nullptr || !st.empty()) {
if(node != nullptr) {
st.push(node);
node = node->left;
}
else {
node = st.top();
st.pop();
ans.push_back(node->val);
node = node->right;
}
}
return ans;
}
};统一迭代写法
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> ans;
if(root != nullptr) {
st.push(root);
}
while(!st.empty()) {
TreeNode* cur = st.top();
if(cur != nullptr) {
TreeNode* node = cur;
st.pop();
if(node->right) {
st.push(node->right);
}
st.push(node);
st.push(nullptr);
if(node->left) {
st.push(node->left);
}
}
else {
st.pop();
TreeNode* node = st.top();
ans.push_back(node->val);
st.pop();
}
}
return ans;
}
};145. 二叉树的后序遍历 - 力扣（LeetCode）
我的AC代码
递归写法
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
void travel(TreeNode* t, vector<int>& ans) {
if(t == nullptr) {
return;
}
travel(t->left, ans);
travel(t->right, ans);
ans.push_back(t->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
travel(root, ans);
return ans;
}
};迭代写法
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
if(root == nullptr) {
return ans;
}
st.push(root);
while(!st.empty()) {
TreeNode* node = st.top();
ans.push_back(node->val);
st.pop();
if(node->left != nullptr) st.push(node->left);
if(node->right != nullptr) st.push(node->right);
}
reverse(ans.begin(), ans.end());
return ans;
}
};统一迭代写法
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> ans;
if(root == nullptr) {
return ans;
}
st.push(root);
while(!st.empty()) {
TreeNode* node = st.top();
if(node != nullptr) {
TreeNode* tmp = node;
st.push(nullptr);
if(tmp->right) {
st.push(tmp->right);
}
if(tmp->left) {
st.push(tmp->left);
}
}
else {
st.pop();
TreeNode* tmp = st.top();
st.pop();
ans.push_back(tmp->val);
}
}
return ans;
}
};总结
今天把前中后序遍历二叉树这三道题目又分别用递归法，迭代法，统一迭代法写了一遍，加深了印象，信息量比较大，要把整个过程完全搞懂比较困难，花了很多时间。但是最终复盘写思路的时候感觉不是很好用语言来描述，非要解释只能是把代码用白话文翻译一遍。在我看来，这三种办法本质上其实都是递归，虽然后面两个是迭代，但实际上是利用栈来模拟递归，或许这是我很难把思路描绘出来的原因，也可能单纯是我太菜了。
随机写了一道简单题，居然要用到KMP+动态规划，但貌似是因为数据量很小可以直接暴力所以被划为了简单题，感觉很折磨，debug了半个多小时，不过好在也算是回忆了一下KMP写法，模板基本上手就能写出来，不得不说初始化j = -1写着比较顺手。
相当于复习了一天，一言以蔽之。
Comments NOTHING