首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
牛客734077141号
浙江大学 计算机类
发布于浙江
关注
已关注
取消关注
@mtgo666:
二叉树的三种遍历(非递归)
1、简介我们在递归的时候说到过,一般我们如果想把递归的算法转换至非递归的实现,我们可以自己利用辅助栈来代替系统栈保存一些信息。所以在实现二叉树的三种非递归遍历的时候,我们需要开辟一个辅助栈来保存一些信息。2、二叉树结点结构/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { }};*/3、先序遍历2.1 实现思路我们只需要开辟一个栈,先让根节点入栈。只要栈不空,我们循环的访问栈内每一位结点,如果访问的当前结点有孩子,让结点的右孩子左孩子依次入栈即可。(因为栈是先进后出,先序遍历是根左右,所以我们入栈的时候是先让右孩子入栈)。3.2 代码实现class Solution {public: void preorderTraversal(TreeNode* root) { stack<TreeNode*> s; s.push(root); while(!s.empty()){ TreeNode *temp = s.top(); s.pop(); if(!temp) continue; cout<<temp->val<<" "; if(temp->right) s.push(temp->right); if(temp->left) s.push(temp->left); } }};4、中序遍历4.1 实现思路中序遍历的顺序是左根右,所以我们要先要访问到最左的那个结点(while(t){t= t->left})。在访问最左结点的过程中将路径上的结点入栈。然后当栈不为空的时候循环访问即可。比如说最左的结点是1号结点,其父节点是2号结点。那么在找1号结点的过程中2号结点必定已入栈并且在1号结点下面。所以访问完1号结点后,接着会访问2号结点,只需在访问完2号结点时,将当前指针指向其右子树就会去访问其右子树。总体下来的顺序就是左根右。4.2 代码实现class Solution {public: void inorderTraversal(TreeNode* root) { stack<TreeNode*> s; TreeNode *t = root; while(!s.empty() || t){ while(t){ //找到最左的那个结点 s.push(t); t = t -> left; } if(!s.empty()){ TreeNode *temp = s.top(); s.pop(); cout<<temp->val<<" "; t = temp->right; } } }};5、后序遍历5.1 实现思路后序遍历的非递归实现相较于先序和中序有点复杂。因为我们需要记录下结点的状态,后序遍历的顺序是左右根,我们在访问完左孩子去访问右孩子的时候,要经过根节点,所以我们要记录一下根结点的状态,如果这个根节点访问过了才输出。5.2 代码实现由于要记录每个结点的状态,我们有两种可以实现的方式:第一种是在二叉树结点的结构体内加一个标志位;第二种是我们采用对组的形式,每个结点绑定一个bool值。在这里我们使用对组的方式实现。class Solution {public: void postorderTraversal(TreeNode* root) { stack<pair<TreeNode*, bool> > s; s.push(make_pair(root, false)); //根节点入栈 bool visited; while(!s.empty()){ pair<TreeNode*, bool> p = s.top(); s.pop(); visited = p.second; if(!p.first){ continue; } if(visited){ //如果该节点被访问过才输出 cout<<p.first->val<<" "; } else { s.push(make_pair(p.first, true)); if(p.first->right) s.push(make_pair(p.first->right, false)); if(p.first->left) s.push(make_pair(p.first->left, false)); } } }};
点赞 0
评论 0
全部评论
推荐
最新
楼层
网易互娱
校招火热招聘中
官网直投
相关推荐
大杯无糖
05-16 22:05
门头沟学院 计算机类
二本漫漫求职路......
从23年7月份开始找,秋招的时候,一无所知,对于一个二本普通院校的学生,每天做的只能是海投,早上十点,打开boss直聘,用三十分钟投递满100份。 大致扫一眼,只要符合就嘎嘎投递,虽然我在校学的是golang,但是到现在为止,大部分的面试都是侧重于后端开发,不局限于具体的语言。 秋招投递了一个月,效果不理想,工资低的不想去,工资高的投递不进去。 还记得最初投递的时候,总是忍不住想盯着手机看boss回复没有,约到一场面试能激动高兴好久......最终海投了两个月,八月底面过了北京的一个初级算法工程师,九月底入职了。主要是搞python的,自己一点也没看过python,创业小公司,工资给的也挺高,...
查看3道真题和解析
春招你拿到offer了吗
点赞
评论
收藏
转发
牛客545265457号
今天 10:55
北京邮电大学 计算机类
腾讯PCG后端开发 挑战最速OC
5.13 一面5.15 二面5.16 主管面5.17早上 HR面 结束完后云证5.20 HR打电话确认是否能接offer 说大概5.21 5.22给offer5.21 早上收到offer邮件之前面了一个半月,一个offer也没,感谢腾子,光速完成所有流程,化身鹅小子了
投递腾讯等公司10个岗位 >
点赞
评论
收藏
转发
坚定的芒果在debug
04-29 15:52
已编辑
门头沟学院 电子信息类
是不是我太老实了,丢了一个面试机会
如题我担心的是万一拿了offer,又去不了。市外的得考完期末才能去,得到6月底7月初。怎么办,求助!
点赞
评论
收藏
转发
今天训练dp了吗
04-28 05:55
西交利物浦大学 计算机类
求佬们鞭打一下我寒酸的简历
大三双非天崩开局第一次写简历想暑期随便找个班(实习)上(数据清洗之类的都行)一是不太清楚走什么方向(目前想走java后端)二是学的比较驳杂,没什么专精(算法,前端(框架),数分都会点,但远不到实习的程度)三是时间比较紧迫,正在准备语言和申研。想问问佬们有没有什么对简历和规划上的建议。(目前的计划是在不耽误绩点和语言的基础上,补一补java全家桶)请佬们畅所欲言,救救孩子😭😭😭
点赞
评论
收藏
转发
火鸡帽
05-15 15:21
已编辑
环保技工学校 计算机类
勤思科技
广州小公司线下面准备好一个你全程参与的项目(自己做的,什么都行)+ 一点点八股就可以上了。redis命令? 项目用到的地方? 数据结构?redis穿透和击穿区别?你知道redis内存多大吗?不懂mysql关键字,基础命令。项目中最大的表的字段?写一条sql说一下项目中任意一个全链路开发过程?仔细说hashmap底层?负载因子为什么是这个?答了期望你自己开发时用到的开发工具?你接口怎么验证正确性?怎么确定你的数据是正确的?反正就全程项目细问。会问很细的细节,有些我就不写了。没自己做过项目就别面了,心态会崩
查看13道真题和解析
点赞
评论
收藏
转发
点赞
收藏
评论
分享
回复帖子
提到的真题
返回内容
全站热榜
1
...
因为找实习和女朋友分手了
8867
2
...
写在最后,一个大专人9年的自述
7399
3
...
【有奖活动】浅聊一下我的实习⭐
7249
4
...
换导师
7100
5
...
爱华信华等华
6650
6
...
荣耀一面
5902
7
...
双非本 腾讯WXG暑期已offer | 附面经
5872
8
...
开摆了,写小说去了
5833
9
...
没offer的我们也很优秀偶
5783
10
...
华为暑期开奖
5068
正在热议
#
牛客帮帮团来啦!有问必答
#
840549次浏览
13232人参与
#
机械制造薪资爆料
#
321895次浏览
3747人参与
#
晒一晒我的offer
#
3486987次浏览
55444人参与
#
金三银四,你有感觉到吗
#
331546次浏览
4241人参与
#
0offer是寒冬太冷还是我太菜
#
430628次浏览
4959人参与
#
实习生如何通过转正
#
27937次浏览
364人参与
#
互联网公司评价
#
85469次浏览
1141人参与
#
我在牛爱网找对象
#
51260次浏览
336人参与
#
运营面经
#
15287次浏览
316人参与
#
海康威视求职进展汇总
#
102704次浏览
1224人参与
#
如何缓解入职前的焦虑
#
36157次浏览
357人参与
#
毕业租房也有小确幸
#
27379次浏览
1496人参与
#
国企vs私企,你更想去?
#
20779次浏览
214人参与
#
荣耀求职进展汇总
#
72882次浏览
743人参与
#
投了多少份简历才上岸
#
60859次浏览
981人参与
#
实习必须要去大厂吗?
#
14383次浏览
234人参与
#
你遇到过哪些神仙同事
#
19179次浏览
282人参与
#
如何写一份好简历
#
277655次浏览
4127人参与
#
实习生应该准时下班吗
#
81399次浏览
598人参与
#
如果可以选,你最想从事什么工作
#
187542次浏览
3100人参与
牛客网
牛客企业服务