一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 692|回复: 12
收起左侧

[CareerCup] 【第三轮】7.14-7.20 CareerCup 4.8

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-7-15 08:35:34 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
4.8 You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of Tl.
A tree T2 is a subtree of Tl if there exists a node n in Tl such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.

回复解法可以按照以下格式来
【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】


Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎讨论,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改。

grassgigi 发表于 2014-7-15 09:35:18 | 显示全部楼层
【解题思路】
Recursion:
Check is subtree from root node.
If not recursively call function on both left subtree and right subtree.

【时间复杂度】
O(N*M) -  N is large tree, M is the one with small amount of nodes

【空间复杂度】
O(Height of N + Height of M)

【gist link】
https://gist.github.com/chrislukkk/905c242ada37ac3caf95
Helper class: https://gist.github.com/chrislukkk/2a1f825b8e924ea773e8
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-7-15 11:21:48 | 显示全部楼层
【解题思路】
traverse T1 by level order
check whether the value of nodes in T1 and T2 equal each other.

【时间复杂度】
O(mn) worst case


【空间复杂度】
O(logm + logn)



【gist link】
https://gist.github.com/happyWinner/00db927f38cd2955e3cf

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

donnice 发表于 2014-7-18 04:59:52 | 显示全部楼层
【解题思路】
check if b1 has the root of b2, if not, return false; if true, check the value of nodes one by one(here use an arraylist)
【时间复杂度】
O(mn)
【空间复杂度】
O(n)
【gist】
https://github.com/donnice/donnice/blob/master/Q4_8
【Test】
                     5                                                               
                2                  8                              
          1          4       7                                          
                3         6   
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-18 05:15:30 | 显示全部楼层
【解题思路】
Firstly, do pre-order traversal for T1 to find a node equals to the root of T2;
Then check if this subtree of T1 is the same with tree T2;
【时间复杂度】
O(n+km)
where n is the number of nodes in T1, m is the number of nodes in T2, k is the number of nodes in T1 that are equal to the root of T2;
The worst case is O(m*n)
【空间复杂度】
O(log m + log n)  for recursion calls
【gist link】 https://gist.github.com/jyhjuzi/2c5192865cd2fefdaaf6

回复 支持 反对

使用道具 举报

renli3000 发表于 2014-7-18 09:12:52 | 显示全部楼层
【解题思路】
一开始被百万的数据量给搞糊涂了,以为一棵树装不到内存里必须要拆分啊有木有
后来无耻的翻了下书,发现其实思路和自己开始想的是一样的,都是先比较root,然后再比较subtree,然后就是写2个简单的第归
另外书上第一种解法好奇葩有木有。。。
【时间复杂度】
O(mn)
【空间复杂度】
O(n)
【gist】
https://gist.github.com/Noahsark/2b021566d3862b4bb20c
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-7-18 23:33:03 | 显示全部楼层
【解题思路】Recursion: if the subtree node is in the tree, when find the node then check if it is the subtree; else check the left and right side of the tree.

【时间复杂度】
O(N*M) -  N is large tree, M is the one with small amount of nodes

【空间复杂度】
O(N)

【gist link】https://gist.github.com/bitcpf/b85b3ee344637593a88d
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-19 02:16:24 | 显示全部楼层
【解题思路】
search for T2's root in T1, call the helper function to determine whether it is a subtree.
【时间复杂度】
O(N+kM)
worst case: O(MN)
【空间复杂度】
O(logM+logN)
【gist link】
https://gist.github.com/1575900cb5e3e74211bc
【test case】
pay attention to empty tree cases
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-7-19 08:17:12 | 显示全部楼层
【解题思路】Compare root compare subtree then recursion
【时间复杂度】o(mn)
【空间复杂度】o(n)
【gist link】https://gist.github.com/hilda8519/794e24eb177b5523698e
回复 支持 反对

使用道具 举报

tonygxxx1212 发表于 2014-7-19 23:22:08 | 显示全部楼层

【解题思路】Compare root compare subtree then recursion
【时间复杂度】o(n+km) k is how many times we check subtree  , n for T2, m for T1
【空间复杂度】o(n)
【gist link】https://gist.github.com/xun-gong/178f0cdc80688dd09b84
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-7-22 10:42:09 | 显示全部楼层
【解题思路】
Recursively check if t2 is the subtree of t1, the check is also a recursive function which checks whether two tree match or not.
【时间复杂度】
O(MN)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/iwilbert/96e4a0e45b2142f058e0
回复 支持 反对

使用道具 举报

头像被屏蔽
serolins 发表于 2014-7-22 21:27:09 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-8-14 04:23:28 | 显示全部楼层
好久不来,上次说暂时休息后就一下子拉下来了 >.< 继续
【解题思路】
for all nodes in T1 that the same as the root of T2, check if this is the subtree of T1 that the same as T2
【时间复杂度】
O(n+km)
worst case : O(m*n)
ps: n--Node# in t1
     m--Node# in t2
      k--occurence of t2 root in t1
【空间复杂度】
O(log m + log n)  for recursion calls
【gist link】 https://gist.github.com/JoyceeLee/690e6bba1b4631aa9fff
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 20:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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