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

Question

我试图在二叉搜索树中找到比给定值更高的值的数量，只是为了乐趣和过度学习。到目前为止，我已经通过在纸上绘制其逻辑来编写了一个递归函数。但是，当我运行它时，它没有给出预期的结果。例如，BST 中包含 30, 25, 98, 23, 28, 97, 99, 29。我试图获得比 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，十分配值 a 为 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;