270 Closest Binary Search Tree Value

270. Closest Binary Search Tree Value

1.Question

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.

2. Implementation

(1) Binary Search

class Solution {
    public int closestValue(TreeNode root, double target) {
        TreeNode curNode = root;
        int res = root.val;

        while (curNode != null) {
            if (curNode.val == target) {
                return curNode.val;
            }
            else if (Math.abs(curNode.val - target) < Math.abs(res - target)) {
                res = curNode.val;
            }
            curNode = curNode.val < target ? curNode = curNode.right : curNode.left;
        }
        return res;
    }
}

3. Time & Space Complexity

Binary Search: 时间复杂度: O(logn)， 空间复杂度: O(1)