y****n
发帖数: 192 | 1 今天又做coding面试了，上来就要写个函数 返回二叉排序树的第k个最小的node。
我写了一半，感觉不对劲。请大侠赐教。 | y*******g
发帖数: 6599 | 2 要写的话肯定是in -order到一个数组 最好写吧
【在 y****n 的大作中提到】
: 今天又做coding面试了，上来就要写个函数 返回二叉排序树的第k个最小的node。
: 我写了一半，感觉不对劲。请大侠赐教。
| M***0
发帖数: 1180 | | y****n
发帖数: 192 | 4 哎，我知道应该使用中序遍历，但有点忘了。然后又在考虑quickselect,然后就傻了。
【在 y*******g 的大作中提到】
: 要写的话肯定是in -order到一个数组 最好写吧
| M***0
发帖数: 1180 | 5 pre-order吧，怎么会是in-order
网上有现成的把bst转成sorted link list的程序，拿来改一下，加个计数器就是。不
用额外space | y*******g
发帖数: 6599 | 6 in-order得到排序的数组,,这样要extra space 不过写起来肯定最快最不容易错了
【在 M***0 的大作中提到】
: pre-order吧，怎么会是in-order
: 网上有现成的把bst转成sorted link list的程序，拿来改一下，加个计数器就是。不
: 用额外space
| M***0
发帖数: 1180 | | k***g
发帖数: 75 | 8 不需要另外的数组，就数访问过几个node了，访问到第k个就是要找到。
【在 y*******g 的大作中提到】
: in-order得到排序的数组,,这样要extra space 不过写起来肯定最快最不容易错了
| y*******g
发帖数: 6599 | 9 赞, 正解
【在 k***g 的大作中提到】
: 不需要另外的数组，就数访问过几个node了，访问到第k个就是要找到。
| g*******y
发帖数: 1930 | 10 如果你知道每个子树的元素个数，那么就是个很简单的二分查找。
可以把算子树元素个数的递归算法，跟查找kth node的算法合并在一起。
#define MP(a,b) make_pair((a),(b))
#define INVALID 0
pair find(Node *root, int k){ //return {count, kth element}
if(k<=0) return (k-1,INVALID);
if(root == 0) return MP(0,INVALID);
pair l,r;
l = find(root->left, k);
if(l.first == k) return l;
if(l.first == k-1) return MP(k,root->data);
int k2 = k-1-l.first;
r = find(root->right, k2);
if(r.first == k2) return (k, r.second);
【在 y****n 的大作中提到】
: 今天又做coding面试了，上来就要写个函数 返回二叉排序树的第k个最小的node。
: 我写了一半，感觉不对劲。请大侠赐教。
| y****n
发帖数: 192 | 11 我就是因为这样想才走了弯路。。。
【在 g*******y 的大作中提到】
: 如果你知道每个子树的元素个数，那么就是个很简单的二分查找。
: 可以把算子树元素个数的递归算法，跟查找kth node的算法合并在一起。
: #define MP(a,b) make_pair((a),(b))
: #define INVALID 0
: pair find(Node *root, int k){ //return {count, kth element}
: if(k<=0) return (k-1,INVALID);
: if(root == 0) return MP(0,INVALID);
: pair l,r;
: l = find(root->left, k);
: if(l.first == k) return l;
|
|
