r*****e
发帖数: 146 | |
K*********n
发帖数: 2852 | 2 这个……如果没有其他信息只能深度优先广度优先了。就得O(n)了……
【在 r*****e 的大作中提到】
: 如何随机找二叉树中的任意节点？ 谢谢！
|
g****y
发帖数: 240 | 3 是给一个值找一个节点，还是说随机返回二叉树中的一个节点？
【在 r*****e 的大作中提到】
: 如何随机找二叉树中的任意节点？ 谢谢！
|
r*****e
发帖数: 146 | 4 随机返回一个树中的节点
TreeNode* get_random_node(TreeNode* root);
【在 g****y 的大作中提到】
: 是给一个值找一个节点，还是说随机返回二叉树中的一个节点？
|
b***m
发帖数: 5987 | 5 要求概率完全平均吗？时间上有要求吗？
【在 r*****e 的大作中提到】
: 随机返回一个树中的节点
: TreeNode* get_random_node(TreeNode* root);
|
g****y
发帖数: 240 | 6 那就traversal 所有的节点，然后用reservior sampling
【在 r*****e 的大作中提到】
: 随机返回一个树中的节点
: TreeNode* get_random_node(TreeNode* root);
|
r*****e
发帖数: 146 | 7 概率平均, 时间上没有
【在 b***m 的大作中提到】
: 要求概率完全平均吗？时间上有要求吗？
|
p*****2
发帖数: 21240 | 8
这样应该就可以了吧？
【在 g****y 的大作中提到】
: 那就traversal 所有的节点，然后用reservior sampling
|
b***m
发帖数: 5987 | 9
这个，可以把所有node展开存到数组里吧，然后调用随机数。这个问题问得很含糊啊！
【在 r*****e 的大作中提到】
: 概率平均, 时间上没有
|
l*****a
发帖数: 14598 | 10 放啥数组，任意order traverse,每个按照1/k的概率决定用当前还是原来的。
【在 b***m 的大作中提到】
:
: 这个，可以把所有node展开存到数组里吧，然后调用随机数。这个问题问得很含糊啊！
|
|
|
b***m
发帖数: 5987 | 11
说详细些？
【在 l*****a 的大作中提到】
: 放啥数组，任意order traverse,每个按照1/k的概率决定用当前还是原来的。
|
l*****a
发帖数: 14598 | 12 k=1;
for each node
{
1/K的可能性使用当前node,
1-1/K的可能性使用上次的结果
k++;
}
【在 b***m 的大作中提到】
:
: 说详细些？
|
r*****e
发帖数: 146 | 13 写了一个。弱问一句，初始ret的时候有些糊涂。一定要遍历的第一个？
TreeNode* get_random_node(TreeNode* root){
srand(time(NULL));
InOrderNextIterator it(root);
int cnt = 0;
int j = 0;
TreeNode* ret = root;//or一定要遍历的第一个？也就是in-order的最小？
TreeNode* cur = NULL;
while(it.has_next()){
cur = it.next();
cnt++;
j = rand()%cnt;
if(0 == j)
ret = cur;
}
return ret;
} |
l*******b
发帖数: 2586 | 14 噢，有道理呀，只要遍历树结构就无所谓了跟一个一个取是一样的
【在 l*****a 的大作中提到】
: 放啥数组，任意order traverse,每个按照1/k的概率决定用当前还是原来的。
|
b***m
发帖数: 5987 | 15
俺愚钝呀，还是没看懂。
【在 l*******b 的大作中提到】
: 噢，有道理呀，只要遍历树结构就无所谓了跟一个一个取是一样的
|
l*******b
发帖数: 2586 | 16 http://en.wikipedia.org/wiki/Reservoir_sampling
貌似就是前面说的这个reservoir sampling. 要遍历一遍整个树的
【在 b***m 的大作中提到】
:
: 俺愚钝呀，还是没看懂。
|
p*****2
发帖数: 21240 | 17
InOrderNextIterator it(root);
你这是什么东西呢？
【在 r*****e 的大作中提到】
: 写了一个。弱问一句，初始ret的时候有些糊涂。一定要遍历的第一个？
: TreeNode* get_random_node(TreeNode* root){
: srand(time(NULL));
: InOrderNextIterator it(root);
: int cnt = 0;
: int j = 0;
: TreeNode* ret = root;//or一定要遍历的第一个？也就是in-order的最小？
: TreeNode* cur = NULL;
: while(it.has_next()){
: cur = it.next();
|
p*****2
发帖数: 21240 | 18
TreeNode ans=null;
int count=0;
Random rand=new Random();
void getRandNode(TreeNode root)
{
if(root==null) return;
count++;
if(rand.nextInt(count)==0)
ans=root;
getRandNode(root.left);
getRandNode(root.right);
}
【在 b***m 的大作中提到】
:
: 俺愚钝呀，还是没看懂。
|
w****x
发帖数: 2483 | 19 这题不就是做烂了的那道google的无限输入流随机取数吗 |
b***m
发帖数: 5987 | 20
我就是笨，没看懂你的思想。
【在 p*****2 的大作中提到】
:
: TreeNode ans=null;
: int count=0;
: Random rand=new Random();
:
: void getRandNode(TreeNode root)
: {
: if(root==null) return;
:
: count++;
|
|
|
l*****a
发帖数: 14598 | 21 这个写的很清楚了吧？
k=1;
for each node
{
1/K的可能性使用当前node,
1-1/K的可能性使用上次的结果
k++;
}
【在 b***m 的大作中提到】
:
: 我就是笨，没看懂你的思想。
|
b***m
发帖数: 5987 | 22
不懂耶，我有够笨了吧。
【在 l*****a 的大作中提到】
: 这个写的很清楚了吧？
: k=1;
: for each node
: {
: 1/K的可能性使用当前node,
: 1-1/K的可能性使用上次的结果
: k++;
: }
|
l*****a
发帖数: 14598 | 23 看看http://en.wikipedia.org/wiki/Reservoir_sampling
把它跟BT traverse结合起来
【在 b***m 的大作中提到】
:
: 不懂耶，我有够笨了吧。
|
b***m
发帖数: 5987 | |
b***m
发帖数: 5987 | 25
有些明白了。反正就是要把整个树都遍历一遍呗。对吧？
【在 p*****2 的大作中提到】
:
: TreeNode ans=null;
: int count=0;
: Random rand=new Random();
:
: void getRandNode(TreeNode root)
: {
: if(root==null) return;
:
: count++;
|
p*****2
发帖数: 21240 | 26
对。
【在 b***m 的大作中提到】
:
: 有些明白了。反正就是要把整个树都遍历一遍呗。对吧？
|
b***m
发帖数: 5987 | 27 这个跟我想的不一样。为什么不能事先遍历一次树，把节点全部存在一个数组里，然后
随机取？否则岂不是每次都要遍历？ |
p*****2
发帖数: 21240 | 28
如果树很大，你没有内存建立你的数组咋办？
【在 b***m 的大作中提到】
: 这个跟我想的不一样。为什么不能事先遍历一次树，把节点全部存在一个数组里，然后
: 随机取？否则岂不是每次都要遍历？
|
b***m
发帖数: 5987 | 29
了解。我以前的行业没有太大数据量，讲究的是空间换时间。所有常用的浮点数运算我
们都做成大表一次性load到内存里，需要计算的时候到表里查。
【在 p*****2 的大作中提到】
:
: 如果树很大，你没有内存建立你的数组咋办？
|
Y********f
发帖数: 410 | 30 这个最好是能在节点中存子树的节点数吧，如果是平衡树的话随机查找/插入/删除都是
logN
【在 r*****e 的大作中提到】
: 如何随机找二叉树中的任意节点？ 谢谢！
|
|
|
d*********g
发帖数: 154 | 31 练习一个
class RandomNodeGetterInBinaryTree
{
private static int totalNumNodesSoFar = 0;
private static TreeNode result = new TreeNode();
public TreeNode GetRandomNodeInBinaryTree(TreeNode root)
{
PreOrderTraverse(root);
return result;
}
private void PreOrderTraverse(TreeNode node)
{
if(node == null) return;
ReservoirSampling(node);
PreOrderTraverse(node.left);
PreOrderTraverse(node.right);
}
private void ReservoirSampling(TreeNode node)
{
++totalNumNodesSoFar;
Random random = new Random();
int j = random.nextInt(totalNumNodesSoFar)+1;
if(j <= 1)
{
result = node;
}
}
} |
