Comment on page

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

## 代码

### Approach #1 Recursive Inorder O(n)

/**
* 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) {
List<Integer> nums = new ArrayList();
inorder(root, nums);
return Collections.min(nums, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return Math.abs(o1 - target) - Math.abs(o2 - target);
}
});
}
private void inorder(TreeNode root, List<Integer> nums) {
if (root == null) return;
inorder(root.left, nums);
inorder(root.right, nums);
}
}

### Approach #2 Iterative Inorder

class Solution {
public int closestValue(TreeNode root, double target) {
long pred = Long.MIN_VALUE;
while (!stack.isEmpty() || root != null) {
while (root != null) {
root = root.left;
}
root = stack.removeLast();
if (pred <= target && target < root.val) {
return Math.abs(pred - target) ? (int)pred : root.val;
}
pred = root.val;
root = root.right;
}
return (int)pred;
}
}
class Solution {
public int closestValue(TreeNode root, double target) {
int val, closest = root.val;
while (root != null) {
val = root.val;
closest = Math.abs(val - target) < Math.abs(closest - target) ? val : closest;
root = target < root.val ? root.left : root.right;
}
return closest;
}
}