找到比BST中的给定值更高的值的数字
问题描述:
我试图找到比二进制搜索树中的给定值更高的数值,以获得乐趣和学习过度。我已经用纸上的逻辑书写了迄今为止的一项索取功能。但是,当我运行它时,它没有给出预期的结果。例如,BST中包含30, 25, 98, 23, 28, 97, 99, 29
。我试图获得比28
更大的值应该是5
,但输出是2
。方法中的问题在哪里?我遍历树中的所有节点,是否有更高效的解决方案?找到比BST中的给定值更高的值的数字
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,因为这个逻辑:
不要紧,有多少水平要求,因为订单下降的操作。 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;
感谢您的回复,但我不明白为什么只有2结果。但是,即使在改为括号后,我的方法仍然有错误。 – snr
我刚才也注意到你正在将本地节点结果添加到左侧和右侧。您应该只添加一次本地节点结果。根据本地节点结果将左侧和右侧添加到0或1。我可以在30分钟左右看更多。对不起,现在不能做更多。 – pacifier21
你能根据你的回复编辑你的答案吗? – snr