当前位置:网站首页>Iterative version of preorder traversal, inorder traversal, and postorder traversal of binary tree
Iterative version of preorder traversal, inorder traversal, and postorder traversal of binary tree
2022-08-08 21:03:00 【Thirty to learn】
二叉树前序遍历、中序遍历、Iterative version of post-order traversal
- 前序遍历
void preorder(TreeNode* root)
{
if(root==NULL)
return;
stack<TreeNode*> s;
while(root||!s.empty())
{
while(root)
{
//...处理root
s.push(root);
root=root->left;
}
root=s.top();
s.pop();
root=root->right;
}
}
- 中序遍历
void midorder(TreeNode* root)
{
if(root)
cout<<"empty!"<<endl;
stack<int> s;
while(root||!s.empty())
{
while(root)
{
s.push(root);
root=root->left;
}
root=s.top();
s.pop();
//...处理root
root=root->right;
}
}
- 后序遍历
void postorder(TreeNode* root)
{
stack<TreeNode*> s;
TreeNode * p = root;
TreeNode * lastVisited = NULL;//Record the last visited node
if(p == NULL)
return ans;
while(!s.empty() || p)
{
//Keep iterating to the left child,直到左孩子为空,At the same time, the nodes on the path are pushed onto the stack
if(p)
{
s.push(p);
p = p->left;
}
//此时p==NULL,Reached the lower left corner node
else
{
p = stk.top();
//右孩子为空,Or the right child has already visited the last time
if(p->right == NULL || p->right == lastVisited)
{
//...处理p
lastVisited = p;//更新lastVisited
s.pop();
p = NULL;
}
else{
p = p->right;//这时p是第一次被访问,The value it points to cannot be accessed directly,should visit the right subtree first
}
}
}
return ans;
}
Preorder traversal is basically the same as inorder traversal,The access node location is different,Post-order traversal is relatively complex,关键在于lastvisited的追踪.
边栏推荐
- go基于泛型实现继承
- Gradle简单到使用kotlin编写到常用命令
- 新库上线 | CnOpenData信息传输、软件和信息技术服务业工商注册企业基本信息数据
- Process实现守护线程
- 目标检测论文 Bridng the Gap Between Anchor-based and Anchor-free Detection via ATSS
- 关于KotlinAndroid遇到的小知识
- Jenkins下载安装
- 第十三届蓝桥杯(Web 应用开发)线上模拟赛【第十题】(RESTful API 开发)
- keras调用load_model时报错ValueError: Unknown layer:*解决办法
- 去噪论文 Attention-Guided CNN for Image Denoising
猜你喜欢
随机推荐
EasyExcel上传文件并使用Postman测试
Kotlin delegate property knowledge points
用固态U盘让你的办公环境随身移动
去噪论文 Attention-Guided CNN for Image Denoising
安全策略及电商购物订单简单用例
Fastdata极数:元宇宙报告2022——Hello Metaverse
GeoServer入门学习:03-快速入门
关于KotlinAndroid遇到的小知识
1天搞定单片机中断——基础知识大全
Flask 教程 第一章:Hello, World!
Flask 教程 第十章:邮件支持
磁控胶囊胃镜:具有良好耐受性的非侵入性胃镜检查
rancher坑记录
【Oracle的NVL函数用法】
去噪论文 Beyond a Gaussian Denoiser: Residual Learning of Deep CNN for Image Denoising
Educational Codeforces Round 112 D. Say No to Palindromes
【导出PDF-项目应用】
Redis Bloom Filter
并发和并行——从线程,线程池到任务
jmeter简单压测