【C++】非递归实现二叉树的前中后序遍历
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
🌠 作者@阿亮joy.
🎆专栏《吃透西嘎嘎》
🎇 座右铭每个优秀的人都有一段沉默的时光那段时光是付出了很多努力却得不到结果的日子我们把它叫做扎根
目录
👉二叉树的前序遍历👈
前序遍历的顺序是根、左子树、右子树。那么首先访问的一定是左路节点再来访问左路节点的右子树。而访问左路节点的右子树又可以看成一个子问题那么就能像递归访问整棵树了。
思路
- 想定义一个栈
st
、一个vector v
和一个TreeNode* cur
cur
初始化为root
。- 当
cur
不为空或者st
不为空时while
继续。while
循环里做一下操作左路节点入栈的同时尾插到v
中那么左路节点就访问完了。然后取出栈顶节点top
将cur
置为top->right
这样就可以转化成子问题去访问左路节点的右子树了。cur
不为空表示要访问一棵树st
不为空表示还有左路节点的右子树没有访问。两个同时为空时while
循环结束得到正确的前序遍历。- 注一个节点出栈意味着这个节点及其左子树已经访问完了还剩右子树没有访问。
class Solution
{
public:
vector<int> preorderTraversal(TreeNode* root)
{
stack<TreeNode*> st;
vector<int> v;
TreeNode* cur = root;
// cur 不为空表示要访问一棵树
// st 不为空表示还有右子树没有访问
while(cur || !st.empty())
{
// 开始访问整棵树
// 1.访问左路节点
while(cur)
{
v.push_back(cur->val);
st.push(cur);
cur = cur->left;
}
// 转化成子问题:访问左路节点的右子树
TreeNode* top = st.top();
st.pop();
cur = top->right; // 子问题访问右子树
}
return v;
}
};
👉二叉树的中序遍历👈
中序遍历的顺序是左子树、根、右子树。首先和中序遍历一样的是左路节点入栈入栈的同时不能访问该节点即不能将节点的值尾插到vector
中。当左路节点出栈时表示当前节点的左子树已经访问完了开始访问当前节点及其右子树。
class Solution
{
public:
vector<int> inorderTraversal(TreeNode* root)
{
stack<TreeNode*> st;
vector<int> v;
TreeNode* cur = root;
while(cur || !st.empty())
{
// 1.左路节点入栈
while(cur)
{
st.push(cur);
cur = cur->left;
}
// 2.当左路节点出栈时表示左子树已经访问过了应该
// 访问这个节点和它的右子树
TreeNode* top = st.top();
st.pop();
v.push_back(top->val); // 访问这个节点
cur = top->right; // 转化成子问题访问右子树
}
return v;
}
};
👉二叉树的后序遍历👈
后序遍历的顺序是左子树、右子树、根需要将左子树和右子树访问完了才能访问根。如果栈顶节点为空或者栈顶节点的右子树已经访问过了就可以访问栈顶节点了。为了知道是否已经访问过栈顶节点的右子树我们可以通过prev
来记录上一次访问的节点。当prev
等于top->right
时表示栈顶节点的右子树已经访问过了可以弹出栈顶节点并访问它。
class Solution
{
public:
vector<int> postorderTraversal(TreeNode* root)
{
vector<int> v;
stack<TreeNode*> st;
TreeNode* cur = root;
TreeNode* prev = nullptr;
while(cur || !st.empty())
{
// 左路节点入栈
while(cur)
{
st.push(cur);
cur = cur->left;
}
TreeNode* top = st.top(); // 取栈顶节点但不pop
// 栈顶节点右子树为空或者上一次访问的节点是top右子树的根说明右子树已经访问过了
// 可以访问栈顶节点否则转换成子问题访问top的右子树
if(top->right == nullptr || top->right == prev)
{
st.pop();
v.push_back(top->val);
prev = top;
cur = nullptr; // cur为空表示弹出的栈顶节点没有右子树或者右子树已经访问过了
}
else
cur = top->right;
}
return v;
}
};
👉总结👈
本篇的非递归实现二叉树的前中后序遍历都差不多是一个思路左路节点先入栈。最大的区别就是栈顶节点的访问时机不同。那么以上就是本篇博客的全部内容了如果大家觉得有收获的话可以点个三连支持一下谢谢大家💖💝❣️