我有一个方法,假设在 O(n) 时间内从 BST 获取随机节点。但是,它始终返回根节点。我的方法逻辑有什么问题?
public Node getRandomNode(Node root) {
// get random value between 0 to size of BST
Random ran = new Random();
int ranNum = ran.nextInt(size + 1);
Node temp = root;
return getRandomNode(ranNum, temp);
}
int count = 0;
public Node getRandomNode(int ranNum, Node temp) {
if (temp == null)
return null;
count++;
if(count <= ranNum) {
temp.left = getRandomNode(ranNum, temp.left);
if(count == ranNum)
return temp;
temp.right = getRandomNode(ranNum, temp.right);
}
return temp;
}
最佳答案
如果你看看你在做什么,你会发现无论你在做什么,你唯一返回的就是 temp。在第一次调用 getRandomNode(...) 时,您的 temp 是根节点,并且您永远不会修改 temp。因此,您将始终返回根节点。
为了解决此问题,请尝试以下操作:
if(count <= ranNum) {
temp = getRandomNode(ranNum, temp.left);
if(count == ranNum)
return temp;
temp = getRandomNode(ranNum, temp.right);
}
return temp;
关于java - BST 的随机节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38363698/