f*****s
发帖数: 141 | 1 Given a Binary Search Tree, write a program to print the kth smallest
element without using any static/global variable.
什么方法最好？ |
s*******s
发帖数: 1568 | |
f*****s
发帖数: 141 | 3 In-order traverse always generate value-sorted output, right? So, just use
in-order searching, traverse from 1st element until the k-th element. Is
this correct? |
d*j
发帖数: 13780 | 4 肯定是对的， 人家又要问 有没有 better way ?
这也是肯定的
【在 f*****s 的大作中提到】
: In-order traverse always generate value-sorted output, right? So, just use
: in-order searching, traverse from 1st element until the k-th element. Is
: this correct?
|
b******v
发帖数: 1493 | 5 如果k<=n/2，可以从最小元开始做k-1次FindNext
如果k>n/2，可以从最大元开始做n-k次FindPrevious
时间复杂度O(k'*log(n))，其中k' = min{k, n-k+1}
【在 f*****s 的大作中提到】
: Given a Binary Search Tree, write a program to print the kth smallest
: element without using any static/global variable.
: 什么方法最好？
|
k*******d
发帖数: 1340 | 6 用in-order search能不使用global variable吗？search的时候得用个变量来记录这搜
索到第几个元素了吧？然后当这个变量等于k的时候，停止搜索。这个变量算是global
variable/static variable吗？
我觉得如果要用递归实现这个遍历的话难以避免要用到这个global variable/static
variable吧， 所以这个题的关键应该是不用递归来实现inorder遍历吧，答案可以
google到 |
f*********g
发帖数: 207 | 7 isn't it k'+o(log(n))?
【在 b******v 的大作中提到】
: 如果k<=n/2，可以从最小元开始做k-1次FindNext
: 如果k>n/2，可以从最大元开始做n-k次FindPrevious
: 时间复杂度O(k'*log(n))，其中k' = min{k, n-k+1}
|
