java - BST 的随机节点

Question

我有一个方法，假设在 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;

}

Answer 1

如果你看看你在做什么，你会发现无论你在做什么，你唯一返回的就是 temp。在第一次调用 getRandomNode(...) 时，您的 temp 是根节点，并且您永远不会修改 temp。因此，您将始终返回根节点。

为了解决此问题，请尝试以下操作:

if(count <= ranNum) {
    temp = getRandomNode(ranNum, temp.left);
    if(count == ranNum)
        return temp;
    temp =  getRandomNode(ranNum, temp.right);
}

return temp;