Lintcode 900. 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.

Example

Example1

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

Example2

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

Notice

• 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.

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86

/**  * Definition of TreeNode:  * public class TreeNode {  *     public int val;  *     public TreeNode left, right;  *     public TreeNode(int val) {  *         this.val = val;  *         this.left = this.right = null;  *     }  * }  */   public class Solution {     /**      * @param root: the given BST      * @param target: the given target      * @return: the value in the BST that is closest to the target      */     public int closestValue(TreeNode root, double target) {         // write your code here         int floor = getFloor(root, target);         int ceil = getCeil(root, target);                   if (floor == Integer.MIN_VALUE) {             return ceil;         }                   if (ceil == Integer.MIN_VALUE) {             return floor;         }                   if (Math.abs(floor - target) < Math.abs(ceil - target)) {             return floor;         } else {             return ceil;         }     }           private int getFloor(TreeNode root, double target) {         TreeNode p = root;         TreeNode parent = null;                   while (p != null) {             if ((double)p.val == target) {                 return p.val;             }                           if (p.val < target) {                 parent = p;                 p = p.right;             } else {                 p = p.left;             }         }                   if (parent == null) {             return Integer.MIN_VALUE;         }                   return parent.val;     }           private int getCeil(TreeNode root, double target) {         TreeNode p = root;         TreeNode parent = null;                   while (p != null) {             if ((double)p.val == target) {                 return p.val;             }                           if (p.val < target) {                 p = p.right;             } else {                 parent = p;                 p = p.left;             }         }                   if (parent == null) {             return Integer.MIN_VALUE;         }                   return parent.val;     } }