Как этот алгоритм работает, как ожидалось? Несмотря на переполнение - PullRequest
1 голос
/ 09 марта 2019

Я пытаюсь решить эту проблему :

Учитывая непустое двоичное дерево поиска и целевое значение, найдите в BST значение, наиболее близкое кцель.

Примечание: заданное целевое значение является плавающей точкой.У вас гарантированно есть только одно уникальное значение в BST, которое ближе всего к цели.

Это решение, которое я видел в сети:

public int closestValue(TreeNode root, double target) { 
        int ret = root.val;
        while(root!=null) {
            if(Math.abs(target - root.val)  > Integer.MAX_VALUE){
                System.out.println( " Underflow!");
            }
            if(Math.abs(target - root.val) < Math.abs(target -ret)){
                ret = root.val;
            }
            root = (target < root.val)? root.left : root.right;
        }
        return ret;

    }

Я рассматриваюконтрольный пример:

[1500000000,1400000000] 
-1500000000.0

, где 1500000000 - родительский узел, 1400000000 - левый потомок, а -1500000000.0 - цель.Я бы ожидал, что код будет потерян в предложении Math.abs (что он и делает), потому что -1500000000 - 1500000000 больше, чем Int.MIN_VALUE.Но я не понимаю, как алгоритм все еще возвращает 1400000000.Не должен ли недостаточный уровень привести к сбою сравнения?

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...