欢迎来到数据结构专栏~~二叉树的非递归遍历
(꒪ꇴ꒪(꒪ꇴ꒪ ),我是Scort目前状态：大三非科班啃C++中博客主页：张小姐的猫~江湖背景快上车，握好方向盘跟我有一起打天下嘞！送给自己的一句鸡汤樂：真正的大师永远怀着一颗学徒的心作者水平很有限，如果发现错误，可在评论区指正，感谢欢迎持续关注！
二叉树的非递归遍历
欢迎来到数据结构专栏~~二叉树的非递归遍历1️⃣二叉树的前序遍历2️⃣二叉树的中序遍历3️⃣二叉树的后序遍历
写在最后
1️⃣二叉树的前序遍历
题目链接：传送
本文我们都采用非递归的方法去讲解：
本质上是在模拟递归，因为在递归的过程中使用了系统栈，所以在迭代的解法中常用Stack来模拟系统栈
思路：
二叉树的左子树不断入栈，同时也入数组当左子树都访问完了，要访问右子树的时候，取出栈顶的top元素，并且子问题访问右子树：cur = top->right如此一来可以访问完全部的左右子树
class Solution {
public:
vector
stack
vector
TreeNode* cur = root;
while(cur || !st.empty())
{
//开始访问一颗树的左边节点
while(cur)
{
v.push_back(cur->val);
st.push(cur);
cur = cur->left;
}
//左边节点的右路指针需要访问
TreeNode* top = st.top();
st.pop();
cur = top->right;//子问题访问右树 重点！！
}
return v;
}
};
2️⃣二叉树的中序遍历
题目链接：传送
思路：
要记住中序：左子树 —— 根 —— 右子树当cur 不为空或者栈不为空的时候，就说明还没有遍历完左边节点全部入栈后，遇到空的时候，就要去栈顶top，并且cur = top->right，变到右子树继续
class Solution {
public:
vector
stack
vector
TreeNode* cur = root;
while(cur || !st.empty())
{
//1、左边节点入栈
while(cur)
{
st.push(cur);
cur = cur->left;
}
//2、当左路节点从栈中出来时，应该访问root和右子树了
TreeNode* top = st.top();
st.pop();
v.push_back(top->val);
cur = top->right;
}
return v;
}
};
3️⃣二叉树的后序遍历
题目链接：传送
思路：
和前序中序不一样，访问方式：左子树 —— 右子树 —— 根定义一个prev，来识别已经已经访问过的节点如果遍历完左边节点，右边节点为空or右边节点已经访问过了，则可以访问root
class Solution {
public:
vector
{
stack
vector
TreeNode* cur = root;
TreeNode* prev = nullptr;
while(cur || !st.empty())
{
//1、左节点入栈
while(cur)
{
st.push(cur);
cur = cur->left;
}
//2、当左节点从栈中出来，则表示左子树已经访问过了
TreeNode* top = st.top();
if(top->right == nullptr || top->right == prev)
{
v.push_back(top->val);
prev = top;
st.pop();
}
else
{
cur = top->right;//子问题访问右子树
}
}
return v;
}
};
写在最后
acwing永远滴神
相关链接
您阅读本篇文章共花了：
发表评论