一亩三分地论坛

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

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

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

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

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

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

x
4.7 Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.

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


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


grassgigi 发表于 2014-7-15 09:29:42 | 显示全部楼层
本帖最后由 grassgigi 于 2014-7-15 09:35 编辑

【解题思路】
Recursion

【时间复杂度】
O(N^2) in worst case

【空间复杂度】
O(Height of N) for call stack

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

使用道具 举报

圆梦梦剧场 发表于 2014-7-15 11:12:18 | 显示全部楼层
【解题思路】
recursion


【时间复杂度】
O(n)

【空间复杂度】
O(h)

【gist link】
https://gist.github.com/happyWinner/58853a40c12679d44fb2




回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-7-16 02:34:51 | 显示全部楼层
【解题思路】
recursion 测试是否包含两个节点,然后再确定是 root 还是 其子结点
【时间复杂度】
O(n)
【空间复杂度】
O(?)
【gist link】
https://gist.github.com/JoyceeLee/765c93b3f1c130fc5501
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-7-16 13:12:16 | 显示全部楼层
【解题思路】find a chain p,q on same side. 书里的
(1)p,q are on left side, branch left to look for common ancestor
(2)p,q are on right side, branch right to look for common ancestor
(3)p,q are no longer on same side, find first common ancestor
【时间复杂度】o(n)
【空间复杂度】o(n)
【gist link】https://gist.github.com/hilda8519/fe8866902dc1705e7899
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-7-17 00:36:01 | 显示全部楼层
【解题思路】recursion
if root is null, return null
if root is q/p, return root
if, p,q in different sides, return root
if p,q in the same side, check that side to see if p,q on different sides
【时间复杂度】o(n)
【空间复杂度】o(n)
【gist link】https://gist.github.com/happyWinner/58853a40c12679d44fb2
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-17 08:13:59 | 显示全部楼层
【解题思路】recursion
first check if the tree covers both the two nodes, if not, return false
recursive function:
1. if contains node1 only, return node1
2. if contains node2 only, return node2
3. if contains both, return the first ancestor
【时间复杂度】o(n)
【空间复杂度】o(H) for recursion calls
【gist link】https://gist.github.com/jyhjuzi/f3f546249eb93d3adb7b
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-17 08:14:06 | 显示全部楼层
本帖最后由 jyh橘子 于 2014-7-17 08:16 编辑

【解题思路】recursion
first check if the tree covers both the two nodes, if not, return false
recursive function:
1. if contains node1 only, return node1
2. if contains node2 only, return node2
3. if contains both, return the first ancestor
【时间复杂度】o(n)
【空间复杂度】o(H) for recursion calls
【gist link】https://gist.github.com/jyhjuzi/f3f546249eb93d3adb7b
回复 支持 反对

使用道具 举报

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

使用道具 举报

donnice 发表于 2014-7-18 02:52:44 | 显示全部楼层
【解题思路】
recursion

【时间复杂度】
O(n)
【空间复杂度】
O(h)
【gist link】
https://github.com/donnice/donni ... f40876c5374f77c35dc
【Test】
                      5                                                               
               2                  8                              
         1          4       7                                          
               3         6   
回复 支持 反对

使用道具 举报

renli3000 发表于 2014-7-18 08:19:36 | 显示全部楼层

【解题思路】
Recursion. If one node has the situation: both left and right sub-tree contains one of our nodes, then this is the ancestor we find.

【时间复杂度】
O(n)
【空间复杂度】
O(h)
【gist link】
https://gist.github.com/Noahsark/4847851df110e9819316
回复 支持 反对

使用道具 举报

Neal 发表于 2014-7-18 09:02:23 | 显示全部楼层
【解题思路】Recursion, check how many nodes are found in current node and subtrees, if it's 2, then the current node is the ancestor. Return this node.
【时间复杂度】O(n)
【空间复杂度】O(h)
【gist link】https://gist.github.com/nealhu/d9824c0c3907b8a2c54f
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-18 14:52:24 | 显示全部楼层
【解题思路】
return null pointer if either of the two nodes doesn't exist in the tree; return current root if either node (or both) equal(s) the root; return current root if two nodes belong to different branches; recursively solve for common ancestor if both nodes belong to the same side.
【时间复杂度】
O(N)
【空间复杂度】
O(H)
【gist link】
https://gist.github.com/88b9c5c5179390ca53d4
【test case】
binary search tree: 8 || 3 10 || 1 6 14 || 4 7 13
Common ancester of 3 and 3 is 3
Common ancester of 3 and 6 is 3
Common ancester of 1 and 4 is 3
Common ancester of 6 and 10 is 8
Common ancester of 10 and 13 is 10
Press any key to continue . . .
回复 支持 反对

使用道具 举报

tonygxxx1212 发表于 2014-7-19 23:10:54 | 显示全部楼层
【解题思路】Assumption: when p is one ancestor of q's, we say p is the first common ancestor of p, q
                  Recursion to solve this problem
                      Case 1: p, q locate in different side of root, first common ancestor must be root
                      Case 2: p, q locates in same side of root
                                 sub-case-1: p,q both in left of root , focus on left subtree and recurse on it
                                 sub-case-2: p,q both in right of root, focus on right subtree and recurse on it
                      判断p, q 在不在某subtree也用到了recursion,做的时候没想到,看了答案才知道的
                      整道题就是逻辑+递归,代码量很少,想着费脑
【时间复杂度】O(n)
【空间复杂度】O(h)
【gist link】https://gist.github.com/xun-gong/05fcd99c19eb6b6b1e85
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-7-21 03:11:27 | 显示全部楼层
【解题思路】
check if p and q  do exist in the tree first. then recursively check if p is on the left side, and if q is on the left side.
(1) p and q on the different side of the tree, root is the answer
(2) p and q on left side of the tree, find left subtree
(3) p and q on right side of the tree, find right subtree
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/iwilbert/66236a13a579b9c117d4
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 17:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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