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

**Example:**

```
Input: root = [4,2,5,1,3], target = 3.714286

    4
   / \
  2   5
 / \
1   3

Output: 4
```

time o(logn)

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int closestValue(TreeNode root, double target) {
        if(root == null )
            return -1;
        
        TreeNode floor = getFloor(root,(int)target);
        TreeNode ceiling = getCeiling(root,(int)target+1);
        
        if(!(floor == null && ceiling==null)){
            
            
            if(floor == null || ceiling!=null && Math.abs(target-ceiling.val) < Math.abs(target-floor.val)){
                return ceiling.val;
            }else{
                return floor.val;
            }
        }
        
        return -1;
    }
    
    public TreeNode getFloor(TreeNode root, int target){
        if(root == null)
            return null;
        if(root.val == target)
            return root;
        
        else if(root.val > target){
            return getFloor(root.left,target);
        }else{
            TreeNode n = getFloor(root.right,target);
            return n==null? root:n;
        }
    }
    
    public TreeNode getCeiling(TreeNode root, int target){
        if(root == null)
            return null;
        if(root.val == target)
            return root;
        
        else if(root.val < target){
            return getCeiling(root.right,target);
        }else{
            TreeNode n = getCeiling(root.left,target);
            return n==null? root:n;
        }
    }
}
```

犯错：

1.找到floor 和ceiling后，没有比较

在floor 和ceiling没有同时为空时，第一种情况就是判断floor为空或者ceiling不为空，ceiling离target更近的情况，返回ceiling，不然就返回floor，最后都不满足 返回-1，也就是floor和ceiling都空

2\. floor 和ceiling 传参数传反了

在二的版本上改进的

```java
class Solution{
    public int closestValue(TreeNode root, double target){


        if(root == null) return 0;

        Stack<TreeNode> smallStack = new Stack<>();
        Stack<TreeNode> largeStack = new Stack<>();

        TreeNode cur = root;

        while(cur != null){
            if(cur.val < target){
                smallStack.push(cur);
                cur = cur.right;
            }else{
                largeStack.push(cur);
                cur = cur.left;
            }
        }

        
            //node from small stack diff with target
            double diffS = (smallStack.isEmpty())? Long.MAX_VALUE : Math.abs(smallStack.peek().val - target);
            //node from large stack diff with target
            double diffL = (largeStack.isEmpty()) ? Long.MAX_VALUE: Math.abs(largeStack.peek().val - target);

            if(diffS < diffL){

                return smallStack.peek().val;

            }else{


                return largeStack.peek().val;
            }


    }



}
```