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

我试图在二分搜索树中找到比给定值高的值，这只是为了好玩和过度学习。到目前为止，我已经在纸上画了一个递归函数及其逻辑。但是，当我运行它时，它没有给出预期的结果。例如，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;
}

最佳答案

最后，由于以下逻辑，第一个函数调用将始终最多返回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，十分配一个值为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;