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.
乍一看， 感觉好复杂， 觉得最接近的值或者左子树最大值或者右子树最小值， 如果你也这么想就错了， 因为此时最接近的值应该为root， 啊哈哈~~~w(ﾟДﾟ)w
递归, 但同样是递归， Stefan 大神的就漂亮好多， 膜拜！！！
public int closestValue(TreeNode root, double target) {
TreeNode child = target > root.val ? root.right : root.left;
if(child == null){
return root.val;
}
int val = closestValue(child, target);
return Math.abs(val - target) < Math.abs(root.val - target) ? val : root.val;
}
public int closestValue(TreeNode root, double target) {
if(root == null){
return target < 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
if(target > root.val){
int val = closestValue(root.right, target);
return (Math.abs(val - target) - Math.abs(root.val - target))
< 0 ? val: root.val;
}else if(target < root.val){
int val = closestValue(root.left, target);
return Math.abs(val - target) - Math.abs(root.val - target)
< 0 ? val : root.val;
}else{
return root.val;
}
}
