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.
乍一看， 感覺好復(fù)雜献烦， 覺得最接近的值或者左子樹最大值或者右子樹最小值丢烘， 如果你也這么想就錯(cuò)了， 因?yàn)榇藭r(shí)最接近的值應(yīng)該為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;
? ? ? ? ?}
}
