d********m
发帖数: 101 | 1 Given an unbalanced binary tree, write code to select a node at random (each
node has an equal probability of being selected). |
l******s
发帖数: 3045 | 2 traverse once first to get node total amount, then use this amount as random
domain.
each
【在 d********m 的大作中提到】
: Given an unbalanced binary tree, write code to select a node at random (each
: node has an equal probability of being selected).
|
h*********g
发帖数: 51 | 3 用个计数器C，初始值为1，遍历树的时候以1/C的概率用当前被访问节点的值替换要返
回的值，然后C 1 这样只需遍历一遍 忘了算法的具体名字了 |
a***y
发帖数: 852 | 4 postorder遍历一次，在每个parent节点上返回左右节点总数，有这个信息之后就可以
随机访问了吧 |
l*****z
发帖数: 3022 | 5 有点象算术编码反过来
each
【在 d********m 的大作中提到】
: Given an unbalanced binary tree, write code to select a node at random (each
: node has an equal probability of being selected).
|
r*******e
发帖数: 7583 | 6 https://en.m.wikipedia.org/wiki/Reservoir_sampling
【在 h*********g 的大作中提到】
: 用个计数器C，初始值为1，遍历树的时候以1/C的概率用当前被访问节点的值替换要返
: 回的值，然后C 1 这样只需遍历一遍 忘了算法的具体名字了
|
d****n
发帖数: 397 | 7 按node subtree size 分配概率，然后recursion。1/root.size概率选root，root.
left.size / root.size 概率从left subtree选， root.right.size/root.size从
right subtree选。
each
【在 d********m 的大作中提到】
: Given an unbalanced binary tree, write code to select a node at random (each
: node has an equal probability of being selected).
|
h**p
发帖数: 211 | 8 为什么不能遍历一遍，把node存在array里面，然后用random（1，arr.size） - 1来访
问？ |
c******n
发帖数: 4965 | 9 easy
count total
then select 1 from that range
then go down the preorder traversal. and take n'th node
each
【在 d********m 的大作中提到】
: Given an unbalanced binary tree, write code to select a node at random (each
: node has an equal probability of being selected).
|
r*******e
发帖数: 7583 | 10 需要做两次遍历的不是最佳答案
【在 c******n 的大作中提到】
: easy
: count total
: then select 1 from that range
: then go down the preorder traversal. and take n'th node
:
: each
|
|
|
r*******e
发帖数: 7583 | 11 你觉得面试官会期待这样的答案么
【在 h**p 的大作中提到】
: 为什么不能遍历一遍，把node存在array里面，然后用random（1，arr.size） - 1来访
: 问？
|
c******n
发帖数: 4965 | 12 OK 那也简单， recursive 每个子树， 给出 size 和 要的 random number ， 然后
parent 根据 1/（left size + right size+1） 给自己， 左，右。分概率， 产生
parent 层的 random
【在 r*******e 的大作中提到】
: 需要做两次遍历的不是最佳答案
|
k****i
发帖数: 128 | 13 BinaryTree* randomTreeNode(BinaryTree* root)
{
if(!root) return NULL;
int count=0;
BinaryTree* choice;
randomTreeNode(root, count, choice);
return choice;
}
void preOrder(BinaryTree* root, int& count, BinaryTree*& choice)
{
if(rand()<1/count) {
choice=root;
}
if(root->left) {
count++;
preOrder(root->left, count, choice);
}
if(root->rigth) {
count++;
preOrder(root->right, count, choice);
}
} |
k******a
发帖数: 44 | 14 感觉是访问Kth节点的变形。
一次遍历，给每一个节点加上其下包含的节点的总数。
根节点的总数为n， 那么随机取第n*random()个节点。 |
l***i
发帖数: 1309 | 15 getRandomNode(Node *root) : return pair |
g**4
发帖数: 863 | 16 if(rand()<1/count) {
rand()是什么方法？
【在 k****i 的大作中提到】
: BinaryTree* randomTreeNode(BinaryTree* root)
: {
: if(!root) return NULL;
: int count=0;
: BinaryTree* choice;
: randomTreeNode(root, count, choice);
: return choice;
: }
: void preOrder(BinaryTree* root, int& count, BinaryTree*& choice)
: {
|
k***a
发帖数: 1199 | 17 两遍的方案可以接受，reservoir sampling虽说简单，但是不知道的还是不容易想到
【在 r*******e 的大作中提到】
: 需要做两次遍历的不是最佳答案
|
l******s
发帖数: 3045 | 18 not too far from reservoir sampling, while it's space O(k), yours is always
space O(n), k is the random number, n is the total space. when k == n, that'
s the worst case of reservoir sampling.
【在 h**p 的大作中提到】
: 为什么不能遍历一遍，把node存在array里面，然后用random（1，arr.size） - 1来访
: 问？
|
