P*******b 发帖数: 1001 | 1 记得问过,不过没有搞定。
给一个bst,用递归求第kth节点。要求返回node
不能用额外的空间。bst是普通的bst,node没有子节
点的数目。
thanks |
l*****a 发帖数: 14598 | 2 递归的cost算额外空间吗?
不算的话,直接中根遍历/计数就可以了吧。
【在 P*******b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 记得问过,不过没有搞定。 : 给一个bst,用递归求第kth节点。要求返回node : 不能用额外的空间。bst是普通的bst,node没有子节 : 点的数目。 : thanks
|
s*****n 发帖数: 5488 | 3 先序遍历。
在第一次left == null 时,开始计数。到k时输出。
【在 P*******b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 记得问过,不过没有搞定。 : 给一个bst,用递归求第kth节点。要求返回node : 不能用额外的空间。bst是普通的bst,node没有子节 : 点的数目。 : thanks
|
s*****n 发帖数: 5488 | 4 中序。
【在 s*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先序遍历。 : 在第一次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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 中序。
|
P*******b 发帖数: 1001 | 6 thanks
这个题要求返回node,不然显得太简单。
【在 P*******b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 记得问过,不过没有搞定。 : 给一个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : thanks : 这个题要求返回node,不然显得太简单。
|
P*******b 发帖数: 1001 | 8 呵呵,你试试就知道了
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : i can't get u : then just return node when count==k
|
l*****a 发帖数: 14598 | 9 说说吧
别卖关子了。
有什么区别?
【在 P*******b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 呵呵,你试试就知道了
|
P*******b 发帖数: 1001 | 10 晕,我没有卖关子。
可能是我自己太笨,写不出来。
假设node *p是找到的节点,
if(k == 0) return p在递归的时候只能退到上一级。
除非用额外参数,我是没有什么好办法。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 说说吧 : 别卖关子了。 : 有什么区别?
|
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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 晕,我没有卖关子。 : 可能是我自己太笨,写不出来。 : 假设node *p是找到的节点, : if(k == 0) return p在递归的时候只能退到上一级。 : 除非用额外参数,我是没有什么好办法。
|
c*******t 发帖数: 1095 | |
P********l 发帖数: 452 | 13 我也没测,但是done同学的方法肯定不对。
1。使用了静态变量i,不严格。如何指望在第一层调用时i==0?
2。函数返回的当前层的局部变量。几乎总是返回0。正确的情况才是特例。
【在 d**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我没测试,改写独孤九剑同学的 : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我也没测,但是done同学的方法肯定不对。 : 1。使用了静态变量i,不严格。如何指望在第一层调用时i==0? : 2。函数返回的当前层的局部变量。几乎总是返回0。正确的情况才是特例。
|