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

Microsoft : Judge binary tree equality with swapping allowed

🔗
nooneknow 2011-10-31 12:47:55 | 只看该作者
全局:
啊, 我的code错了, 不能判断在两个节点相等子树交换才相等的情况下, 更正:
wwwyhx 发表于 2011-10-31 12:37


又发现一个概念的歧义。

二叉树equal什么意思?
长得一样就够了?
还是node的值也必须相等。好像都可以。得问interviewer啊。
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-10-31 12:50:51 | 只看该作者
全局:
又发现一个概念的歧义。

二叉树equal什么意思?
长得一样就够了?
还是node的值也必须相等。好像都可以。得问interviewer啊。
nooneknow 发表于 2011-10-31 12:47



    长得一样 && 值相同
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-10-31 12:52:10 | 只看该作者
全局:
回复  wwwyhx


    23 行要返回n1 + n2 +1吧

还有,你没有判断p1,p2里面的数据是不是相同
sunstick 发表于 2011-10-31 12:45


多谢, 更正了
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-10-31 12:54:24 | 只看该作者
全局:
还有个问题 , 怎么优化???
回复

使用道具 举报

🔗
nooneknow 2011-11-1 01:09:53 | 只看该作者
全局:
长得一样 && 值相同
wwwyhx 发表于 2011-10-31 12:50


其实也可以只是长得一样。看interviewer的意思。其实更难了。

如果值也得相同的话,你这样做复杂度太高了。每个node都要swap,指数级复杂度。
这也是我写了两个函数的原因。是不是要交换左右child,可以站在parent的地方判断。
如果不交换或者交换了才相等,在parent那里就能判定了。不需要在children那里swap,分两次递归。
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-11-1 03:07:48 | 只看该作者
全局:
其实也可以只是长得一样。看interviewer的意思。其实更难了。

如果值也得相同的话,你这样做复杂度太高了。每个node都要swap,指数级复杂度。
这也是我写了两个函数的原因。是不是要交换左右child,可以站在parent的地方判断。
如果不交换或者交换了才相等,在parent那里就能判定了。不需要在children那里swap,分两次递归。
nooneknow 发表于 2011-11-1 01:09


好像和我一开始贴的那个差不多.
没看出有什么实际区别, 显然从parent角度判断更让代码繁琐啊.
回复

使用道具 举报

🔗
darksteel 2011-11-1 03:37:30 | 只看该作者
全局:
我觉得8楼那个好像是对的。这样的话应该是n^2复杂度。另外如果求最小交换次数可能还需要改一下代码。目前也没想出什么很好的办法能吧复杂度降下来。
回复

使用道具 举报

🔗
nooneknow 2011-11-1 06:09:02 | 只看该作者
全局:
好像和我一开始贴的那个差不多.
没看出有什么实际区别, 显然从parent角度判断更让代码繁琐啊.
wwwyhx 发表于 2011-11-1 03:07


知道差别在哪里了。
你开始没判断值是不是相等,复杂度成了指数级。
如果判断值的话,应该也是O(n)。没太大差别。交换不交换只有一个return true。

不过都没有考虑重复元素的情况。那样复杂度又是指数级了。
回复

使用道具 举报

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

使用道具 举报

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


8楼正确的, 这题怎么讨论这么长时间, 结贴~~~
回复

使用道具 举报

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

本版积分规则

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