当前位置:网站首页>二叉树的前序,中序,后续(非递归版本)
二叉树的前序,中序,后续(非递归版本)
2022-07-01 15:36:00 【努力变好的zz】
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
前言
二叉树的非递归版本的前序中序后序在面试中也经常考,必须熟练掌握!
下面将会讲如何非递归打印二叉树的前中后序。
一、前序
思路:递归改非递归一般都要用到数据结构栈,当前节点出栈的时候打印,并有右节点先加入右节点,
后加入左节点,因为前序根左右,而栈是逆序,所以先入有节点。
void Print(TreeNode* root)
{
//前序
stack<TreeNode*> s = stack<TreeNode*>();//创建栈
s.push(root);//头结点入栈
入栈顺序有右压右,有左压左
while (!s.empty())
{
TreeNode* cur = s.top();
s.pop();
cout << to_string(cur->val)+"" ;
if (cur->right)
{
s.push(cur->right);
}
if (cur->left)
{
s.push(cur->left);
}
}
}
二、后序
思路:与前序不同,后序我们需要两个栈进行调换,第一个栈得出的结果顺序是根右左,因为栈逆序,我们将s1栈中的数据放入s2就得到了左右根,后续操作和前序相似。
后序
stack<TreeNode*> s1 = stack<TreeNode*>();
stack<TreeNode*> s2 = stack<TreeNode*>();
s1.push(root);
while (!s1.empty())
{
TreeNode* cur = s1.top();
s1.pop();
s2.push(cur);
if (cur->left)
{
s1.push(cur->left);
}
if (cur->right)
{
s1.push(cur->right);
}
}
while (!s2.empty())
{
TreeNode* cur = s2.top();
s2.pop();
cout << cur->val << endl;
}
三、中序
代码如下:
中序
stack<TreeNode*> t = stack<TreeNode*>();
TreeNode* cur = root;
while (!t.empty() || cur!=nullptr)
{
if (cur!= nullptr)
{
t.push(cur);
cur = cur->left;
}
else
{
cur = t.top();
t.pop();
cout << cur->val << endl;
cur = cur->right;
}
}
总结
边栏推荐
- Implementation of deploying redis sentry in k8s
- Task.Run(), Task.Factory.StartNew() 和 New Task() 的行为不一致分析
- MySQL advanced 4
- [target tracking] |stark
- 【ROS进阶篇】第五讲 ROS中的TF坐标变换
- 6.2 normalization 6.2.6 BC normal form (BCNF) 6.2.9 normalization summary
- Recommendation of data acquisition tools and detailed graphic process of data acquisition list
- Tableapi & SQL and MySQL grouping statistics of Flink
- [antenna] [3] some shortcut keys of CST
- 【300+精选大厂面试题持续分享】大数据运维尖刀面试题专栏(三)
猜你喜欢
How to realize clock signal frequency division?
phpcms后台上传图片按钮无法点击
[advanced ROS] lesson 5 TF coordinate transformation in ROS
做空蔚来的灰熊,以“碰瓷”中概股为生?
MySQL 服务正在启动 MySQL 服务无法启动解决途径
Stm32f411 SPI2 output error, pb15 has no pulse debugging record [finally, pb15 and pb14 were found to be short circuited]
智能运维实战:银行业务流程及单笔交易追踪
Zhang Chi Consulting: lead lithium battery into six sigma consulting to reduce battery capacity attenuation
An intrusion detection model
Deep operator overloading (2)
随机推荐
skywalking 6.4 分布式链路跟踪 使用笔记
6.2 normalization 6.2.6 BC normal form (BCNF) 6.2.9 normalization summary
【一天学awk】函数与自定义函数
MySQL 服务正在启动 MySQL 服务无法启动解决途径
Stm32f4-tft-spi timing logic analyzer commissioning record
Rhcsa fourth day operation
Is JPMorgan futures safe to open an account? What is the account opening method of JPMorgan futures company?
Opencv learning notes 5 -- document scanning +ocr character recognition
如何实现时钟信号分频?
Introduction to MySQL audit plug-in
做空蔚来的灰熊,以“碰瓷”中概股为生?
Opencv Learning Notes 6 -- image mosaic
Tableapi & SQL and MySQL grouping statistics of Flink
[cloud trend] new wind direction in June! Cloud store hot list announced
Tableapi & SQL and MySQL insert data of Flink
[300 + selected interview questions from big companies continued to share] big data operation and maintenance sharp knife interview question column (III)
Intelligent operation and maintenance practice: banking business process and single transaction tracking
远程办公经验?来一场自问自答的介绍吧~ | 社区征文
常见健身器材EN ISO 20957认证标准有哪些
Tableapi & SQL and MySQL data query of Flink