P*******b
发帖数: 1001 | 1 记得问过，不过没有搞定。
给一个bst，用递归求第kth节点。要求返回node
不能用额外的空间。bst是普通的bst，node没有子节
点的数目。
thanks |
l*****a
发帖数: 14598 | 2 递归的cost算额外空间吗？
不算的话，直接中根遍历/计数就可以了吧。
【在 P*******b 的大作中提到】
: 记得问过，不过没有搞定。
: 给一个bst，用递归求第kth节点。要求返回node
: 不能用额外的空间。bst是普通的bst，node没有子节
: 点的数目。
: thanks
|
s*****n
发帖数: 5488 | 3 先序遍历。
在第一次left == null 时，开始计数。到k时输出。
【在 P*******b 的大作中提到】
: 记得问过，不过没有搞定。
: 给一个bst，用递归求第kth节点。要求返回node
: 不能用额外的空间。bst是普通的bst，node没有子节
: 点的数目。
: thanks
|
s*****n
发帖数: 5488 | 4 中序。
【在 s*****n 的大作中提到】
: 先序遍历。
: 在第一次left == null 时，开始计数。到k时输出。
|
s*****n
发帖数: 5488 | 5 #include
use namespace std;
void k-bst(Node * root, int k)
{
static int i = 0;
if ( root )
{
K-BST(root->left, k);
if (++i == k)
cout << root->data;
k-bst(root->right,k);
}
}
【在 s*****n 的大作中提到】
: 中序。
|
P*******b
发帖数: 1001 | 6 thanks
这个题要求返回node，不然显得太简单。
【在 P*******b 的大作中提到】
: 记得问过，不过没有搞定。
: 给一个bst，用递归求第kth节点。要求返回node
: 不能用额外的空间。bst是普通的bst，node没有子节
: 点的数目。
: thanks
|
l*****a
发帖数: 14598 | 7 i can't get u
then just return node when count==k
【在 P*******b 的大作中提到】
: thanks
: 这个题要求返回node，不然显得太简单。
|
P*******b
发帖数: 1001 | 8 呵呵，你试试就知道了
【在 l*****a 的大作中提到】
: i can't get u
: then just return node when count==k
|
l*****a
发帖数: 14598 | 9 说说吧
别卖关子了。
有什么区别？
【在 P*******b 的大作中提到】
: 呵呵，你试试就知道了
|
P*******b
发帖数: 1001 | 10 晕，我没有卖关子。
可能是我自己太笨，写不出来。
假设node *p是找到的节点，
if(k == 0) return p在递归的时候只能退到上一级。
除非用额外参数，我是没有什么好办法。
【在 l*****a 的大作中提到】
: 说说吧
: 别卖关子了。
: 有什么区别？
|
d**e
发帖数: 6098 | 11 我没测试，改写独孤九剑同学的
Node * k-bst(Node * root, int k)
{
static int i = 0;
Node * p = 0;
if ( root )
{
if((p = K-BST(root->left, k)) != 0)
;
else if (++i == k)
p = root;
else
p = k-bst(root->right,k);
}
return p;
}
【在 P*******b 的大作中提到】
: 晕，我没有卖关子。
: 可能是我自己太笨，写不出来。
: 假设node *p是找到的节点，
: if(k == 0) return p在递归的时候只能退到上一级。
: 除非用额外参数，我是没有什么好办法。
|
c*******t
发帖数: 1095 | |
P********l
发帖数: 452 | 13 我也没测，但是done同学的方法肯定不对。
1。使用了静态变量i，不严格。如何指望在第一层调用时i==0?
2。函数返回的当前层的局部变量。几乎总是返回0。正确的情况才是特例。
【在 d**e 的大作中提到】
: 我没测试，改写独孤九剑同学的
: Node * k-bst(Node * root, int k)
: {
: static int i = 0;
: Node * p = 0;
: if ( root )
: {
: if((p = K-BST(root->left, k)) != 0)
: ;
: else if (++i == k)
|
b********h
发帖数: 119 | 14 似乎没啥问题啊。
函数的局部静态变量在第一次调用的时候初始化。
一旦找到kth节点之后，它就会被不断的返回到上层的调用，直到根节点，结束函数的
执行。
【在 P********l 的大作中提到】
: 我也没测，但是done同学的方法肯定不对。
: 1。使用了静态变量i，不严格。如何指望在第一层调用时i==0?
: 2。函数返回的当前层的局部变量。几乎总是返回0。正确的情况才是特例。
|
