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

[其他] 前序遍历二叉树的空间复杂度是多少?

🔗
MTC | 只看该作者 |倒序浏览
全局:

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

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

x
O(1)吗?非递归的是logN吧?

上一篇:找一个二叉树上某两个节点的共同祖先,不得使用额外的数据结构,二叉树不一定是BST
下一篇:Return all amicable pairs less than given N
推荐
daihao0310 2014-10-20 23:46:50 | 只看该作者
全局:
时间复杂度:logN
回复

使用道具 举报

🔗
neusharon 2014-10-20 22:55:26 | 只看该作者
全局:
iterative:O(n); recursion:O(n), O(logN) in memory stack.
回复

使用道具 举报

🔗
 楼主| MTC 2014-10-20 22:57:02 | 只看该作者
全局:
neusharon 发表于 2014-10-20 22:55
iterative:O(n); recursion:O(n), O(logN) in memory stack.

迭代不都是用stack的吗?怎么还O(N)?
回复

使用道具 举报

🔗
neusharon 2014-10-20 23:02:26 | 只看该作者
全局:
MTC 发表于 2014-10-20 22:57
迭代不都是用stack的吗?怎么还O(N)?

如果你只是打印的话可以是O(1), 存下来要O(N)
回复

使用道具 举报

🔗
 楼主| MTC 2014-10-20 23:03:40 | 只看该作者
全局:
neusharon 发表于 2014-10-20 23:02
如果你只是打印的话可以是O(1), 存下来要O(N)

存下来时LogN吧,用stack啊
回复

使用道具 举报

🔗
stephenK 2014-10-21 00:54:51 | 只看该作者
全局:
iterative和 recursive 空间复杂度都是logN。 另外有一种O(1)空间的遍历叫做 morris遍历。
回复

使用道具 举报

🔗
 楼主| MTC 2014-10-21 09:17:52 | 只看该作者
全局:
stephenK 发表于 2014-10-21 00:54
iterative和 recursive 空间复杂度都是logN。 另外有一种O(1)空间的遍历叫做 morris遍历。

谢谢,递归和迭代的时间复杂度都是O(N)吧?那为什么说迭代要高效呢?
回复

使用道具 举报

🔗
stephenK 2014-10-22 05:19:02 | 只看该作者
全局:
MTC 发表于 2014-10-20 21:17
谢谢,递归和迭代的时间复杂度都是O(N)吧?那为什么说迭代要高效呢?

是的。
大家练题的时候总是尽量能写成iterative尽量iterative。但在实际应用中,两者对栈空间消耗的区别很小。
而且现在functional programming 越来越火,recursive反而有优势。
回复

使用道具 举报

🔗
 楼主| MTC 2014-10-22 08:12:01 | 只看该作者
全局:
stephenK 发表于 2014-10-22 05:19
是的。
大家练题的时候总是尽量能写成iterative尽量iterative。但在实际应用中,两者对栈空间消耗的区别 ...

他两空间复杂的有些小差别是吧?
回复

使用道具 举报

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

本版积分规则

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