[LintCode] Problem 900 - Closest Binary Search Tree Value

Posted on | In ,

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.

Example

No.1

Input: root = {5,4,9,2,#,8,10} and target = 6.124780

Output: 5

No.2

Input: root = {3,2,4,1} and target = 4.142857

Output: 4

Code

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
public int closestValue(TreeNode root, double target) {
    if (root == null)
        return 0;

    int val;

    if (root.val > target)
        val = closestValue(root.left, target);
    else
        val = closestValue(root.right, target);

    return Math.abs(root.val - target) < Math.abs(val - target) ? root.val : val;
}