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.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    double minDiff = Double.MAX_VALUE;
    int ans = Integer.MAX_VALUE;

    public int closestValue(TreeNode root, double target) {

        if (root == null) return -1;    
        dfs(root, target);

        return ans;
    }

    private void dfs(TreeNode root, double target){
        if (root == null) return;

        if (Math.abs((double)root.val - target) < minDiff){
            minDiff = Math.abs((double)root.val - target);
            ans = root.val;
        }
        dfs(root.left, target);        
        dfs(root.right, target);

    }
}