推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 993|回复: 13
收起左侧

[CareerCup] 【第三轮】7.7-7.13 CareerCup 4.6

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
4.6 Write an algorithm to find the 'next' node (i.e., in-order successor) of a given node in a binary search tree. You may assume that each node has a link to its parent.

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


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



ryancooper 发表于 2014-7-9 02:02:58 | 显示全部楼层
【解题思路】
There are two cases:
1. if the node has right child, then find the minimum element of the subtree rooted at the right of this node. By BST property, this is the successor of our node.
2. if node has no right subtree, then this node must be the maximum of a certain tree. So for the root of this tree, it should be left child of another node N or it is the root of the whole BST. if it is N, then N is our successor, otherwise there is no successor(since we are the right most node of the whole BST).
【时间复杂度】
O(h) (h means height of the tree)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/ryancooper/a87fb60f8f9b7865ecf1
回复 支持 反对

使用道具 举报

grassgigi 发表于 2014-7-9 03:46:13 | 显示全部楼层
【解题思路】
If node's right subtree is not null
        return minimum node of the right subtree
else
        return the first of the node's ancester who has the node in its left sub tree

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

【空间复杂度】
O(1)

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

使用道具 举报

donnice 发表于 2014-7-10 03:14:44 | 显示全部楼层
本帖最后由 donnice 于 2014-7-10 04:53 编辑

【解题思路】
1.一个节点有右孩子,则在中序遍历中,该节点的后继是它的右子树的最左节点。
2. 这个节点是它父亲的左孩子,则该节点的后继节点是它的父亲
3. 这个节点是它父亲的右孩子,则需要一直向上搜索,直到它们n-1代祖先是它第n代祖先的左孩子,则它的后继就是第n个祖先。如果一直搜索到根节点,也没有找到n-1代祖先是它第n代祖先的左孩子,则该节点是整个树的中序遍历中的最后一个节点,即它没有后继。
【时间复杂度】
O(h)(worst)——when the node is on the longer branch
【空间复杂度】
O(1)
https://github.com/donnice/donnice/blob/master/Q4_6
【Test case】
                        5                                                               
             2                  8                              
       1          4       7                                          
             3        
顺便我的代码里写了个getParent的接口,大家有兴趣可以参考下     
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-7-12 01:03:44 | 显示全部楼层
【解题思路】
1. if the node has a right child, return the leftmost node of its right subtree
2. else if the node is the left child of its parent, return its parent
3. else (the node is the right child of its parent) then keep searching upwards the tree until the situation of (2) is found

【时间复杂度】
O(h)


【空间复杂度】
O(1)


【gist link】
https://gist.github.com/happyWinner/e3a6f0601e611d5a59fb

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

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

使用道具 举报

兰橘清檬 发表于 2014-7-13 09:46:45 | 显示全部楼层
【解题思路】
inorder 的下一个节点
1. 有右子结点的话,是右子结点的最左节点
2. 作为左枝上节点出现的根节点
3. 不是以上两者,就是 null
【时间复杂度】
O(H)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/JoyceeLee/0e0409af30f86a9af2de
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-13 14:02:44 | 显示全部楼层
本帖最后由 ivycheung1208 于 2014-7-13 01:04 编辑

【解题思路】
if current node has right child: search for the leftmost node in the right subtree and return that node
if not: search backwards until a node that is left child of its parent, return the parent; or until reach the root, return null.
【时间复杂度】
O(H)
worse case: O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/3febb995ce4af53c8f67
【test case】
this algorithm does not limit to binary search tree. applicable with any binary tree.
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-7-14 07:21:45 | 显示全部楼层
【解题思路】
the parent of root is null
(1) if node.right not null, the next node the the min of the right subtree or the leftmost of right subtree
(2) if node is in the parent's left subtree, the next node is the parent
(3) if node is in the parent's right subtree, go up and find the ancestor which is the left child of its parent, the next node is the ancestor's parent
【时间复杂度】
O(H) - height of the tree
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/iwilbert/5842b8f26cc9482fcca3
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-7-14 23:01:53 | 显示全部楼层
【解题思路】
(1) if node.has right child, return the right child
(2) else, if the node is on left of the parent, return the parent node
(3) if node is in parent's right, go up and find the ancestor which is the left child of its parent, the next node is the ancestor's parent
【时间复杂度】
O(H) - height of the tree
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/bitcpf/0f9a508eb9692a9362b2
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-7-16 10:57:36 | 显示全部楼层
【解题思路】1. if the node has a right child, return the leftmost node of its right subtree
2. else if the node is the left child of its parent, return its parent
3. else (the node is the right child of its parent) then keep searching upwards the tree until the situation of (2) is found
【时间复杂度】o(n)
【空间复杂度】o(n)
【gist link】https://gist.github.com/hilda8519/b5f7b62a0ae43c9a98f1
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-17 06:30:04 | 显示全部楼层
【解题思路】
two cases:
1.  node has a right child.  Then the next node is the most left node of its right subtree;
2.  node has no right child.  Then we need to find the first ancestor that is the left child of its own parent.  then the parent is exactly the node we need.  If we reach root before find the needed node, we should return null which means there is no next node.
【时间复杂度】 O(H)
【空间复杂度】 O(1)
【gist link】 https://gist.github.com/jyhjuzi/5d88cc27d9b91c763dcb
回复 支持 反对

使用道具 举报

renli3000 发表于 2014-7-18 06:50:58 | 显示全部楼层
本帖最后由 renli3000 于 2014-7-18 07:14 编辑

【解题思路】
  case1: nood.right == null : traverse to father untile node != node.father.right
  case2: nood.right != null: traverse to right, and find the minimum
其实不用father指针更好做,从root往下找,key小了就记下指针往左,key大了就往右走

【时间复杂度】 O(H)
【空间复杂度】 O(1)
【gist link】
https://gist.github.com/Noahsark/7124940b34eccc34a31a

回复 支持 反对

使用道具 举报

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

【解题思路】
1.  node has a right child.  Then the next node is the most left node of its right subtree;
2.  node has no right child && node <= its parent, next node = parent
2.  node has no right child && node > its parent, keep search for parent of parent until find, else return NULL
【时间复杂度】 O(logn)
【空间复杂度】 O(1)
【gist link】https://gist.github.com/xun-gong/f4497902c29bc0c1cdf5
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-19 15:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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