270. Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

• Given target value is a floating point.
• You are guaranteed to have only one unique value in the BST that is closest to the target.

解题方法

分左右子樹去計算高度

    public int closestValue(TreeNode root, double target) {
        //ending condition
        if(root.left == null && root.right == null){
            return root.val;
        }

        int val = root.val;
        if(root.val == target){
            return root.val;
        }else if(target < root.val){
            if(root.left != null){
                val = closestValue(root.left, target);
            }
        }else{
            if(root.right != null){
                val = closestValue(root.right, target);
            }
        }

        if( Math.abs(target - (double)val) <= Math.abs((double)root.val - target)){
            return val;
        }
        return root.val;
    }


    //Simple
    public int closestValue(TreeNode root, double target) {
        TreeNode kid = target < root.val ? root.left : root.right;
        if (kid == null){ return root.val;}
        int val = closestValue(kid, target);
        return Math.abs(root.val - target) < Math.abs(val - target) ? root.val : val;
    }