LeetCode刷题实战270：最接近的二叉搜索树值

程序员小猿

发布于 2021-05-28 10:52:57

4220

发布于 2021-05-28 10:52:57

文章被收录于专栏：程序IT圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 最接近的二叉搜索树值，我们先来看题面：

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

There is a fence with n posts, each post can be painted with one of the k colors. You have to paint all the posts such that no more than two adjacent fence posts have the same color. Return the total number of ways you can paint the fence. Note: n and k are non-negative integers.

给定一个不为空的二叉搜索树和一个目标值 target，请在该二叉搜索树中找到最接近目标值 target 的数值。

注意：

给定的目标值 target 是一个浮点数

题目保证在该二叉搜索树中只会存在一个最接近目标值的数

示例

示例：
输入: root = [4,2,5,1,3]，目标值 target = 3.714286

    4
   /  \
  2    5
 /  \
1    3

输出: 4

解题

https://cloud.tencent.com/developer/article/1659812

暴力查找

class Solution {
  int ans = LONG_MAX;
  double diff = LONG_MAX;
public:
    int closestValue(TreeNode* root, double target) {
      if(!root) return 0;
      if(fabs(double(root->val)-target) < diff)
      {
        diff = fabs(double(root->val)-target);
        ans = root->val;
      }
      closestValue(root->left, target);
      closestValue(root->right, target);
      return ans;
    }
};

二分查找

class Solution {
  int ans = LONG_MAX;
  double diff = LONG_MAX;
public:
    int closestValue(TreeNode* root, double target) {
      if(!root) return 0;
        if(fabs(double(root->val)-target) < diff)
      {
        diff = fabs(double(root->val)-target);
        ans = root->val;
      }
        if(root->val > target)
            closestValue(root->left, target);
        else
            closestValue(root->right, target);
      return ans;
    }
};

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-05-20，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法