# \*270. Closest Binary Search Tree Value

<https://leetcode.com/problems/closest-binary-search-tree-value/>

## solution

```python
class Solution:
    def closestValue(self, root, target):
        upper = root
        lower = root

        while root:
            if root.val > target:
                upper = root  # 先记录再往后迭代
                root = root.left
            elif root.val < target:
                lower = root
                root = root.right
            else:
                return root.val

        if abs(upper.val - target) > abs(lower.val - target):
            return lower.val
        return upper.val
```

```python
# 一些BST题目甚至可以先中序存为list, 再从list中找到最近的

class Solution(object):
    def closestValue(self, root, target):
        res = None
        cur = root

        while cur:
            # 更直接的思路: 记录遍历过程中距离, 并记录更新距离最小的dian
            if res is None or abs(res - target) > abs(cur.val - target):
                res = cur.val

            if cur.val > target:
                cur = cur.left
            else:
                cur = cur.right
        return res
```

时间复杂度：O(h)\
空间复杂度：O(h)

dfs

```python
class Solution:
    def __init__(self):
        self.low = -float('inf')
        self.high = float('inf')

    def closest_value(self, root: TreeNode, target: float) -> int:
        if not root:
            return

        if root.val <= target:
            self.low = max(self.low, root.val)
            self.closest_value(root.right, target)
        else:
            self.high = min(self.high, root.val)
            self.closest_value(root.left, target)

        if target - self.low > self.high -target:
            return self.high
        else:
            return self.low
```

## follow up

[272. Closest Binary Search Tree Value II](https://leetcode.com/problems/closest-binary-search-tree-value-ii/description/)

```python
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://longxingtan.gitbook.io/mle-interview/01_leetcode/07_dfs/270.-closest-binary-search-tree-value.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.