📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
123
返回列表 发新帖
楼主: wwwyhx
跳转到指定楼层
上一主题 下一主题
收起左侧

Microsoft : Judge binary tree equality with swapping allowed

🔗
nooneknow 2011-11-1 09:49:52 | 只看该作者
全局:
回复  nooneknow
应该达不到O(n)吧,你上面的代码有一个问题,如果左右儿子分别相等,你就直接左边跟左边比,右边跟右边比,这是不完整的。如果左右相等的话,就需要(左左 右右) + (左右 右左)两种情况都试一遍才行。我觉得上面8楼的代码是对的,T(n) = 4T(n/2) + O(1)  T(n) = O(n^2)。这题应该很难再降低复杂度了。
darksteel 发表于 2011-11-1 08:51


不考虑元素duplicates的话,每个node只用扫2遍。复杂度O(2n)。
或者这么想,无论是不是swap,最多只有一个可能性返回true。
需不需要swap,下一层递归马上就能知道。不需要递归下去。
递归式是T(n) = T(n - 1) + O(1)。

如果考虑duplicates,worst case是每个node的值都一样。相当于只比较树长得像不像。
这样每个node都要考虑swap或者不swap。复杂度是指数级。
回复

使用道具 举报

🔗
darksteel 2011-11-1 13:48:34 | 只看该作者
全局:
本帖最后由 darksteel 于 2011-11-1 13:49 编辑

回复 21# nooneknow
同意不考虑重复的复杂度是O(n)。不过考虑重复应该用不了指数。上面8楼的代码很清楚,理想情况树是平衡的,每次去掉一半的节点,T(n)=4T(n/2)+O(1),解出来是T(n)=O(n^2)。如果树不是平衡的代价更小。
你说每个node要考虑swap和不swap的情况是没错,但因为树是分左右子树的,交换前后的代价并不是一样的,不是每个分支都会继续向下深度为n,不太好这么考虑。
有一种更直观的想法:无论如何交换,树A的某个节点只可能跟树B同层的节点做比较,而且最多一次,所以总的比较次数基本上就是两棵树各层的节点的乘积的和。最糟糕情况就是1*1+2*2+4*4+...+(n/2)(n/2)=O(n^2)。
回复

使用道具 举报

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

本版积分规则

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