找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: jbao
收起左侧

[Google] 一道google面试题:find Kth node in BST

  [复制链接]

84

主题

32

精华

1278

积分

顶级会员

Rank: 6Rank: 6

积分
1278

活跃会员热心会员最佳新人精华帖之王

发表于 12-23-2014 11:38 PM | 显示全部楼层
Smilefish 发表于 12-1-2014 10:08 PM0 j( ?, q% ?5 T; b  W/ U  G
如果这个function要被调用很多次,是不是应该用一个算法导论里讲的 Order-Statistic tree? 这样每次找到ran ...

8 W  `% z8 c  U: ]- Q% i这样只要在结点上记录小于它的左子树里有多少个节点,大于它的右子树里有多少个结点。。动态的统计。。。

3

主题

1

精华

61

积分

资深会员

Rank: 2

积分
61
发表于 1-19-2015 05:08 PM | 显示全部楼层
或者在class里弄个instance variable来记录

17

主题

10

精华

340

积分

高级会员

Rank: 3Rank: 3

积分
340
发表于 1-23-2015 07:31 PM | 显示全部楼层
jbao 发表于 12-1-2014 09:31 PM
+ E7 A& ~+ P% ]4 v% Y; C确实,这样就是in order的变种。 不过我觉得没必要用list把之前遍历的记录,只需要有一个count就行

2 S( p( ?3 _8 [. m+ `2 b9 ?0 Ou're right.
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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