# 270. Closest Binary Search Tree Value

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mjd7TgP4CYoi093uPNE%2F-MjdsNsOxSaNXQcLCHyM%2Fimage.png?alt=media\&token=08e4fc05-1cd2-40a3-9495-c299fc6fdc6b)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mjd7TgP4CYoi093uPNE%2F-MjdsQBOWt_B7EVDA-GH%2Fimage.png?alt=media\&token=51b5fca5-a43a-4000-96c0-00fb555fab24)

iteration, 左右走去找到 upper, lower, 最後比較差值

time: O(h), tree height

space: O(1)

可以參考這個

[https://www.jiuzhang.com/problem/closest-binary-search-tree-value/](https://www.jiuzhang.com/problem/closest-binary-search-tree-value/)

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int closestValue(TreeNode root, double target) {
        
        TreeNode upper = root;
        TreeNode lower = root;
        while (root != null) {
            if (root.val > target) {
                upper = root;
                root = root.left;
            } else if (root.val < target) {
                lower = root;
                root = root.right;
            } else {
                return root.val;
            }
        }
        if (Math.abs(upper.val - target) > Math.abs(target - lower.val)) {
            return lower.val;
        }
        return upper.val;
    }
}
```



更精簡的

```java
class Solution {
  public int closestValue(TreeNode root, double target) {
    int val;
    int closest = root.val;
    while(root != null) {
      val = root.val;
      closest = Math.abs(val - target) > Math.abs(closest - target) ? closest : val;
      root = root.val < target ? root.right: root.left;
    }
    
    return closest;
  }
}
```

