> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/tree/270.-closest-binary-search-tree-value.md).

# 270. Closest Binary Search Tree Value

![](/files/-MjdsNsOxSaNXQcLCHyM)

![](/files/-MjdsQBOWt_B7EVDA-GH)

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

time: O(h), tree height

space: O(1)

可以參考這個

<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;
  }
}
```