找到比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，因为这个逻辑：

​​

不要紧，有多少水平要求，因为订单下降的操作。 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;