270_最接近的二叉搜索树值

类型：树

• 270. 最接近的二叉搜索树值 💚

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

  ❓ 在二叉搜索树中找到最接近目标值 target 的数。

  💡 利用搜索树的性质直接在树中搜索

  根据搜索树的性质，如果目标小于当前结点，则向左搜索，如果目标大于当前结点，则向右搜索。

  class Solution:
      def closestValue(self, root: TreeNode, target: float) -> int:
          closest = root.val
          while root:
              closest = min(root.val, closest, key = lambda x: abs(target - x))
              root = root.left if target < root.val else root.right
          return closest

  时间复杂度：O(h)，空间复杂度：O(1)

  💡 中序遍历

  我们对搜索树中序遍历，即可以得到升序序列，从中找出最接近 target 的元素。

  class Solution:
      def closestValue(self, root: TreeNode, target: float) -> int:
          def inorder(r: TreeNode):
              return inorder(r.left) + [r.val] + inorder(r.right) if r else []
  
          return min(inorder(root), key = lambda x: abs(target - x))

  时间复杂度：O(n)，空间复杂度：O(n)

  💡 中序遍历 + 空间优化

  我们不需要得到完整的中序遍历结果再去找元素，由于中序遍历是升序的，我们发现随着元素继续增大，离目标值越来越远（即 nums[i]<=target<nums[i+1]）的话，就不必再关注后面的元素了。