当前位置:网站首页>Preorder, inorder, follow-up of binary tree (non recursive version)
Preorder, inorder, follow-up of binary tree (non recursive version)
2022-07-01 15:38:00 【Try to be better zz】
Tips : When the article is finished , Directories can be generated automatically , How to generate it, please refer to the help document on the right
List of articles
Preface
The pre order, middle order and post order of the non recursive version of the binary tree are also often tested in the interview , Must be proficient in !
Next, we will talk about how to print the first, middle and last sequence of binary tree non recursively .
One 、 Before the order
Ideas : Data structure stack is generally used to change recursion to non recursion , Print when the current node is out of the stack , And a right node is added to the right node first ,
Then add the left node , Because the antecedent root is about , The stack is in reverse order , So first enter the node .
void Print(TreeNode* root)
{
// Before the order
stack<TreeNode*> s = stack<TreeNode*>();// Create a stack
s.push(root);// Head node stack
The order of stacking is right pressing right , There is left pressure left
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);
}
}
}
Two 、 In the following order
Ideas : Different from the previous sequence , In the following sequence, we need two stacks to exchange , The result order of the first stack is root right left , Because the stack is in reverse order , We will s1 Put the data in the stack s2 You get left and right , Subsequent operations are similar to those in the previous sequence .
In the following order
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;
}
3、 ... and 、 Middle preface
The code is as follows :
Middle preface
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;
}
}
summary
边栏推荐
- Short Wei Lai grizzly, to "touch China" in the concept of stocks for a living?
- 【OpenCV 例程200篇】216. 绘制多段线和多边形
- 有些能力,是工作中学不来的,看看这篇超过90%同行
- 如何写出好代码 - 防御式编程指南
- [antenna] [3] some shortcut keys of CST
- 6.2 normalization 6.2.6 BC normal form (BCNF) 6.2.9 normalization summary
- 【目标跟踪】|模板更新 时间上下文信息(UpdateNet)《Learning the Model Update for Siamese Trackers》
- Recommendation of data acquisition tools and detailed graphic process of data acquisition list
- JS中箭头函数和普通函数的区别
- Gaussdb (for MySQL):partial result cache, which accelerates the operator by caching intermediate results
猜你喜欢
随机推荐
ABAP-调用Restful API
An intrusion detection model
Shopping mall 6.27 to be completed
使用 csv 导入的方式在 SAP S/4HANA 里创建 employee 数据
做空蔚来的灰熊,以“碰瓷”中概股为生?
MySQL service is starting. MySQL service cannot be started. Solution
Don't ask me again why MySQL hasn't left the index? For these reasons, I'll tell you all
Survey of intrusion detection systems:techniques, datasets and challenges
[Cloudera][ImpalaJDBCDriver](500164)Error initialized or created transport for authentication
MySQL审计插件介绍
[Cloudera][ImpalaJDBCDriver](500164)Error initialized or created transport for authentication
异常检测中的浅层模型与深度学习模型综述(A Unifying Review of Deep and Shallow Anomaly Detection)
她就是那个「别人家的HR」|ONES 人物
Qt+pcl Chapter 6 point cloud registration ICP series 3
The difference between arrow function and ordinary function in JS
Day 3 of rhcsa study
张驰课堂:六西格玛数据的几种类型与区别
《QT+PCL第九章》点云重建系列2
贝联珠贯加入龙蜥社区,共同促进碳中和
ABAP-屏幕切换时,刷新上一个屏幕