leetcode_day14

本文最后更新于 2024年8月18日 下午

今日内容:
- 递归遍历
- 迭代遍历
- 统一迭代

三道例题:

前序遍历二叉树
中序遍历二叉树
后续遍历二叉树

递归遍历

太过简单,skip

迭代遍历(非统一版)

使用栈模拟递归过程:

前序就是先访问当前节点值,然后压栈右左孩子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> preorderTraversal(TreeNode* root) {
if(root == nullptr) return {};
stack<TreeNode*> st;
TreeNode * cur = root;
st.push(cur);
vector<int> ans;
while(!st.empty()) {
cur = st.top();
st.pop();
ans.push_back(cur->val);
if(cur->right) st.push(cur->right);
if(cur->left) st.push(cur->left);
}
return ans;
}

中序就是先存所有左节点,直到遇null再出栈栈顶,访问值后压栈右节点(压栈的所有节点均不为空)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> inorderTraversal(TreeNode* root) {
if(!root) return {};
stack<TreeNode*> st;
vector<int> ans;
TreeNode * cur = root;
while(!st.empty() || cur != nullptr) {
if(cur != nullptr) {
st.push(cur);
cur = cur->left;
}
else {
cur = st.top();
st.pop();
ans.push_back(cur->val);
cur = cur->right;
}
}
return ans;
}

后序比较讨巧,左右中倒序就是中右左,把前序的压栈顺序调换,最后翻转结果就行,就不贴代码了

统一迭代遍历

形式统一的迭代遍历,主要思想是压栈null标记下一个节点需要访问,这样写出来的代码在压栈部分就可以只调换顺序实现三种遍历

个人感觉比较好理解,最好记住写法,下面以后序为例给出代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode *> st;
TreeNode * cur = root;
if(cur != nullptr)st.push(cur);
while(!st.empty()) {
cur = st.top();
if(cur != nullptr) {
st.pop();

st.push(cur);
st.push(nullptr);//中

if(cur->right) st.push(cur->right);//右

if(cur->left) st.push(cur->left);//左
}
else {
st.pop();
cur = st.top();
ans.push_back(cur->val);
st.pop();
}
}
return ans;
}

leetcode_day14
https://novelyear.github.io/2024/06/04/leetcode-day14/
作者
Leoo Yann
更新于
2024年8月18日
许可协议