📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 5404| 回复: 13
跳转到指定楼层
上一主题 下一主题
收起左侧

Ananimous : 不用队列/堆栈,层次遍历一颗树

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
设计一种数据结构,不用队列/堆栈能够层次遍历一颗树

上一篇:Microsoft(5) : 字符串最大回文子串
下一篇:Ananimous : 找出数组和之差最小的两部分
🔗
ljfljf2006 2011-4-23 14:09:04 | 只看该作者
全局:
我不是很明白楼主的意思。

不能用队列/堆栈,那是可以用数组? 如果可以用数组的话,那其实就可以用数组实现堆栈了。

如果是队列/堆栈/数组都不让用,那我能想到的就是用迭代了。可是迭代本质也就是堆栈了。
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-4-23 14:41:39 | 只看该作者
全局:
我不是很明白楼主的意思。

不能用队列/堆栈,那是可以用数组? 如果可以用数组的话,那其实就可以用数组实现堆栈了。

如果是队列/堆栈/数组都不让用,那我能想到的就是用迭代了。可是迭代本质也就是堆栈了。
ljfljf2006 发表于 2011-4-23 14:09


数组实现堆栈的功能,当然还是堆栈.....
迭代你怎么做?? 用其他数据结构怎么做??
回复

使用道具 举报

🔗
danielgao 2011-4-24 00:49:56 | 只看该作者
全局:
回复 1# wwwyhx


这个要求很模糊啊,我用最小堆算用了堆栈不?
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-4-24 01:45:50 | 只看该作者
全局:
回复  wwwyhx


这个要求很模糊啊,我用最小堆算用了堆栈不?
danielgao 发表于 2011-4-24 00:49


额,原题是不用队列实现层次遍历,亚马逊的题目。后来我想用两个堆栈也能实现队列,就加了队列的性质,只要不是拐弯抹角实现队列的都成
回复

使用道具 举报

🔗
greenphoto 2011-4-24 09:38:40 | 只看该作者
全局:
以前好像看到过这道题,节点属性中要多一个指向父节点的指针
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-4-24 10:40:00 | 只看该作者
全局:
以前好像看到过这道题,节点属性中要多一个指向父节点的指针
greenphoto 发表于 2011-4-24 09:38



    不能改变原结构,一个节点只有左指针,右指针和兄弟指针
回复

使用道具 举报

🔗
danielgao 2011-4-24 11:23:45 | 只看该作者
全局:
额,原题是不用队列实现层次遍历,亚马逊的题目。后来我想用两个堆栈也能实现队列,就加了队列的性质,只要不是拐弯抹角实现队列的都成
wwwyhx 发表于 2011-4-24 01:45


我觉得这题的本质就是要用队列啊,我觉得题目的意思就是不能直接用队列而已吧,不然我用最小堆弄个优先队列出来其实本质还是队列。。
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-4-24 12:18:58 | 只看该作者
全局:
我觉得这题的本质就是要用队列啊,我觉得题目的意思就是不能直接用队列而已吧,不然我用最小堆弄个优先队列出来其实本质还是队列。。
danielgao 发表于 2011-4-24 11:23



    的确是有不用类似队列的很clever的解法,我不清楚是否题的意思是要用其他数据结构类似实现队列功能,如果这样就觉得没太大意思了。
    给个提示,如果做中序遍历的话,从各个层次的角度来看,节点的先后顺序是正确的,问题是把这些层次间参差的节点分到各个层上面去。
回复

使用道具 举报

🔗
danielgao 2011-4-24 12:57:38 | 只看该作者
全局:
的确是有不用类似队列的很clever的解法,我不清楚是否题的意思是要用其他数据结构类似实现队列功能,如果这样就觉得没太大意思了。
    给个提示,如果做中序遍历的话,从各个层次的角度来看,节点的先后顺序是正确的,问题是把这些层次间参差的节点分到各个层上面去。
wwwyhx 发表于 2011-4-24 12:18


你之前有一篇POST提到可以有兄弟指针?
是的话,做2次DFS,第一次找到最大深度。
第二次的时候当找到深度与最大深度相同的节点的时候,利用兄弟指针把那层的兄弟节点都打光,然后
递归实现的话很自然就能返回上一层,再把上一层的的都打了,一直返回打到最顶层。
   
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表