请教红菜苔种下去后# gardening - 拈花惹草
L*t
1 楼
ind median of a BST, with out any extra memory and with out using any
gloabal
or static variables.
gloabal
or static variables.
m*i
2 楼
那末大的间距是不是太奢侈了，大家就这样空着？我的香菜没出几根，可以这个间距里
补吗？还是插些大蒜头，或洒点菜籽？谢谢各位先。
补吗？还是插些大蒜头，或洒点菜籽？谢谢各位先。
r*o
3 楼
extra memory是什么意思啊？临时变量都不能有吗？还是说不能有数组?
【在 L****t 的大作中提到】
: ind median of a BST, with out any extra memory and with out using any
: gloabal
: or static variables.
【在 L****t 的大作中提到】
: ind median of a BST, with out any extra memory and with out using any
: gloabal
: or static variables.
g*e
4 楼
所以我都是单独育苗，等比较大了再栽到地里。
你这种情况最好种些短平快的，比如鸡毛菜，红菜苔长大后套种的就得拔了。
【在 m****i 的大作中提到】
: 那末大的间距是不是太奢侈了，大家就这样空着？我的香菜没出几根，可以这个间距里
: 补吗？还是插些大蒜头，或洒点菜籽？谢谢各位先。
你这种情况最好种些短平快的，比如鸡毛菜，红菜苔长大后套种的就得拔了。
【在 m****i 的大作中提到】
: 那末大的间距是不是太奢侈了，大家就这样空着？我的香菜没出几根，可以这个间距里
: 补吗？还是插些大蒜头，或洒点菜籽？谢谢各位先。
L*t
5 楼
我也不是很清楚啊，感觉是应该不能有数组，stack queue这类的
是CareerCup上的题目。
【在 r****o 的大作中提到】
: extra memory是什么意思啊？临时变量都不能有吗？还是说不能有数组?
是CareerCup上的题目。
【在 r****o 的大作中提到】
: extra memory是什么意思啊？临时变量都不能有吗？还是说不能有数组?
c*p
6 楼
对哦，回去就撒
莴笋苗们都站起来了，喀喀！
【在 g***e 的大作中提到】
: 所以我都是单独育苗，等比较大了再栽到地里。
: 你这种情况最好种些短平快的，比如鸡毛菜，红菜苔长大后套种的就得拔了。
莴笋苗们都站起来了，喀喀！
【在 g***e 的大作中提到】
: 所以我都是单独育苗，等比较大了再栽到地里。
: 你这种情况最好种些短平快的，比如鸡毛菜，红菜苔长大后套种的就得拔了。
b*r
7 楼
两个指针都不许有？
【在 L****t 的大作中提到】
: ind median of a BST, with out any extra memory and with out using any
: gloabal
: or static variables.
【在 L****t 的大作中提到】
: ind median of a BST, with out any extra memory and with out using any
: gloabal
: or static variables.
L*t
8 楼
应该可以把，如果用两个指针，一个从正常的preorder扫过去，
一个是从 右子数开始的Preorder扫过去，两个相同的时候（假设奇数）就是Median，
不过递归中怎么控制这两个指针都同步扫呢。。
或者是先Travel一次算出一共多少个Node，然后再遍历到 n/2 就是Median，
不过算出多少Node的话也算用到static 或者global variable了吧。。
【在 b****r 的大作中提到】
: 两个指针都不许有？
一个是从 右子数开始的Preorder扫过去，两个相同的时候（假设奇数）就是Median，
不过递归中怎么控制这两个指针都同步扫呢。。
或者是先Travel一次算出一共多少个Node，然后再遍历到 n/2 就是Median，
不过算出多少Node的话也算用到static 或者global variable了吧。。
【在 b****r 的大作中提到】
: 两个指针都不许有？
s*f
9 楼
不用global variable就是不能计算node总数目了,但是可以算左右子树的node数目.
比如从root开始,左子树有10个,右子树有20个node(递归),那么就知道median在右子树
里,
而且是第5小的数.在看右子树的两个子树,递归下去直到要求找某个子树的第1小什么之
类的.
我没仔细想,不过大概描述一下,你看看是不是满足要求.
【在 L****t 的大作中提到】
: 应该可以把，如果用两个指针，一个从正常的preorder扫过去，
: 一个是从 右子数开始的Preorder扫过去，两个相同的时候（假设奇数）就是Median，
: 不过递归中怎么控制这两个指针都同步扫呢。。
: 或者是先Travel一次算出一共多少个Node，然后再遍历到 n/2 就是Median，
: 不过算出多少Node的话也算用到static 或者global variable了吧。。
比如从root开始,左子树有10个,右子树有20个node(递归),那么就知道median在右子树
里,
而且是第5小的数.在看右子树的两个子树,递归下去直到要求找某个子树的第1小什么之
类的.
我没仔细想,不过大概描述一下,你看看是不是满足要求.
【在 L****t 的大作中提到】
: 应该可以把，如果用两个指针，一个从正常的preorder扫过去，
: 一个是从 右子数开始的Preorder扫过去，两个相同的时候（假设奇数）就是Median，
: 不过递归中怎么控制这两个指针都同步扫呢。。
: 或者是先Travel一次算出一共多少个Node，然后再遍历到 n/2 就是Median，
: 不过算出多少Node的话也算用到static 或者global variable了吧。。
w*k
10 楼
recursion就在用extra space
【在 s********f 的大作中提到】
: 不用global variable就是不能计算node总数目了,但是可以算左右子树的node数目.
: 比如从root开始,左子树有10个,右子树有20个node(递归),那么就知道median在右子树
: 里,
: 而且是第5小的数.在看右子树的两个子树,递归下去直到要求找某个子树的第1小什么之
: 类的.
: 我没仔细想,不过大概描述一下,你看看是不是满足要求.
【在 s********f 的大作中提到】
: 不用global variable就是不能计算node总数目了,但是可以算左右子树的node数目.
: 比如从root开始,左子树有10个,右子树有20个node(递归),那么就知道median在右子树
: 里,
: 而且是第5小的数.在看右子树的两个子树,递归下去直到要求找某个子树的第1小什么之
: 类的.
: 我没仔细想,不过大概描述一下,你看看是不是满足要求.
h*k
11 楼
可以不用递归遍历树，用循环。
node *lnode=root, *rnode=root;
while( lnode.left != null )
lnode = lnode.left;
while( rnode.right != null )
rnode = rnode.right;
while( lnode.key <= rnode.key )
{
node * next;
if( lnode.right != nul ) // next node should be in lnode's right sub-
tree;
{
next = lnode.right;
while( next.left != nul )
next = next.left;
lnode = next;
}else{ // no right sub-tree, go back to parent node
next = lnode;
whi
【在 L****t 的大作中提到】
: 应该可以把，如果用两个指针，一个从正常的preorder扫过去，
: 一个是从 右子数开始的Preorder扫过去，两个相同的时候（假设奇数）就是Median，
: 不过递归中怎么控制这两个指针都同步扫呢。。
: 或者是先Travel一次算出一共多少个Node，然后再遍历到 n/2 就是Median，
: 不过算出多少Node的话也算用到static 或者global variable了吧。。
node *lnode=root, *rnode=root;
while( lnode.left != null )
lnode = lnode.left;
while( rnode.right != null )
rnode = rnode.right;
while( lnode.key <= rnode.key )
{
node * next;
if( lnode.right != nul ) // next node should be in lnode's right sub-
tree;
{
next = lnode.right;
while( next.left != nul )
next = next.left;
lnode = next;
}else{ // no right sub-tree, go back to parent node
next = lnode;
whi
【在 L****t 的大作中提到】
: 应该可以把，如果用两个指针，一个从正常的preorder扫过去，
: 一个是从 右子数开始的Preorder扫过去，两个相同的时候（假设奇数）就是Median，
: 不过递归中怎么控制这两个指针都同步扫呢。。
: 或者是先Travel一次算出一共多少个Node，然后再遍历到 n/2 就是Median，
: 不过算出多少Node的话也算用到static 或者global variable了吧。。
r*o
12 楼
没看明白，能不能解释一下啊？
【在 h**k 的大作中提到】
: 可以不用递归遍历树，用循环。
: node *lnode=root, *rnode=root;
: while( lnode.left != null )
: lnode = lnode.left;
: while( rnode.right != null )
: rnode = rnode.right;
: while( lnode.key <= rnode.key )
: {
: node * next;
: if( lnode.right != nul ) // next node should be in lnode's right sub-
【在 h**k 的大作中提到】
: 可以不用递归遍历树，用循环。
: node *lnode=root, *rnode=root;
: while( lnode.left != null )
: lnode = lnode.left;
: while( rnode.right != null )
: rnode = rnode.right;
: while( lnode.key <= rnode.key )
: {
: node * next;
: if( lnode.right != nul ) // next node should be in lnode's right sub-
h*k
13 楼
用两个指针，一个从正常的inorder扫过去，
一个是从右往左开始的inorder（即每个树的访问顺序是右子树-根节点-左子树）扫过
去，两个相遇的时候就是median
基本原理：在正常的inorder遍历中，
假设当前访问的点是cur_node，则必然cur_node的左子树已经遍历完毕。如果cur_node
的右子树不为空，则下一个要访问的点是cur_node的右子树上的最小的节点；如果为空
，则需要返回cur_node的父节点，而如果cur_node是它的父亲的右子树 ，则cur_node
的父亲已经访问过，继续上朔，直到找到一个祖先，cur_node在他的左子树上，这个祖
先就是下一个要访问的节点。
【在 r****o 的大作中提到】
: 没看明白，能不能解释一下啊？
一个是从右往左开始的inorder（即每个树的访问顺序是右子树-根节点-左子树）扫过
去，两个相遇的时候就是median
基本原理：在正常的inorder遍历中，
假设当前访问的点是cur_node，则必然cur_node的左子树已经遍历完毕。如果cur_node
的右子树不为空，则下一个要访问的点是cur_node的右子树上的最小的节点；如果为空
，则需要返回cur_node的父节点，而如果cur_node是它的父亲的右子树 ，则cur_node
的父亲已经访问过，继续上朔，直到找到一个祖先，cur_node在他的左子树上，这个祖
先就是下一个要访问的节点。
【在 r****o 的大作中提到】
: 没看明白，能不能解释一下啊？
w*k
14 楼
不是const space吧
node
node
【在 h**k 的大作中提到】
: 用两个指针，一个从正常的inorder扫过去，
: 一个是从右往左开始的inorder（即每个树的访问顺序是右子树-根节点-左子树）扫过
: 去，两个相遇的时候就是median
: 基本原理：在正常的inorder遍历中，
: 假设当前访问的点是cur_node，则必然cur_node的左子树已经遍历完毕。如果cur_node
: 的右子树不为空，则下一个要访问的点是cur_node的右子树上的最小的节点；如果为空
: ，则需要返回cur_node的父节点，而如果cur_node是它的父亲的右子树 ，则cur_node
: 的父亲已经访问过，继续上朔，直到找到一个祖先，cur_node在他的左子树上，这个祖
: 先就是下一个要访问的节点。
node
node
【在 h**k 的大作中提到】
: 用两个指针，一个从正常的inorder扫过去，
: 一个是从右往左开始的inorder（即每个树的访问顺序是右子树-根节点-左子树）扫过
: 去，两个相遇的时候就是median
: 基本原理：在正常的inorder遍历中，
: 假设当前访问的点是cur_node，则必然cur_node的左子树已经遍历完毕。如果cur_node
: 的右子树不为空，则下一个要访问的点是cur_node的右子树上的最小的节点；如果为空
: ，则需要返回cur_node的父节点，而如果cur_node是它的父亲的右子树 ，则cur_node
: 的父亲已经访问过，继续上朔，直到找到一个祖先，cur_node在他的左子树上，这个祖
: 先就是下一个要访问的节点。
h*k
15 楼
如果每个节点有指向父亲的指针，程序里只需保存当前访问的节点。
【在 w******k 的大作中提到】
: 不是const space吧
:
: node
: node
【在 w******k 的大作中提到】
: 不是const space吧
:
: node
: node
相关阅读