java在BST中查找比给定值更高的值的数量

Question

我试图在二元搜索树中找到比给定值更高的值，只是为了好玩和过度学习。到目前为止，我已经通过在纸上绘制其逻辑来编写了一个复活函数。然而，当我运行它时，它并没有给出预期的结果。例如，30, 25, 98, 23, 28, 97, 99, 29包含在BST中。我试图获得大于28应该是5的值，但输出是2。这个方法的问题在哪里？我正在遍历树中的所有节点，有更有效的解决方案吗

public int findMax(Node<E> localRoot, E target) {
        if (localRoot == null) return 0;

        int cmpResult = target.compareTo(localRoot.data);
        int valL = findMax(localRoot.left, target) + cmpResult < 0 ? 1 : 0;
        int valR = findMax(localRoot.right, target) + cmpResult < 0 ? 1 : 0;
        return valL + valR;
}

Answer 1

最后，由于以下逻辑，第一个函数调用始终最多返回1+1：

int valL = findMax(localRoot.left, target) + cmpResult < 0 ? 1 : 0;
int valR = findMax(localRoot.right, target) + cmpResult < 0 ? 1 : 0;

因为操作顺序，它调用了多少级别并不重要。valL和valR将始终为0或1，因为它正在测试（findMax（localRoot.right，target）+cmpResult）是否为<；0，10指定一个0或1的值。尝试使用括号，这样就可以添加到findMax的结果中。像这样：

int valL = findMax(localRoot.left, target) + (cmpResult < 0 ? 1 : 0);
int valR = findMax(localRoot.right, target) + (cmpResult < 0 ? 1 : 0);

编辑

好吧，我意识到我忽略了另一个重要问题：你正在将局部比较结果添加到每个节点的左右计算中。这将导致值过高！您需要保持本地节点比较独立于左、右节点比较。试试这个：

int cmpResult = target.compareTo(localRoot.data);
int localNodeVal = cmpResult < 0 ? 1 : 0; // This is the value for the current node by itself.
int valL = findMax(localRoot.left, target);
int valR = findMax(localRoot.right, target);
// Add the local node result with the evaluation of the left and right side.
return localNodeVal + valL + valR;