给一棵非空二叉搜索树以及一个 target 值，找到在 BST 中最接近给定值的节点值

• 给出的目标值为浮点数
• 我们可以保证只有唯一一个最接近给定值的节点

→做题地址

样例 1

输入: root = {5,4,9,2,#,8,10} and target = 6.124780 输出: 5 解释： 二叉树 {5,4,9,2,#,8,10}，表示如下的树结构：         5        /       4    9     /    /     2    8  10  

样例 2

输入: root = {3,2,4,1} and target = 4.142857 输出: 4 解释： 二叉树 {3,2,4,1}，表示如下的树结构：      3     /    2    4  / 1  

[题解]

算法很简单，求出 lowerBound 和 upperBound 。即 < target 的最大值和 >= target 的最小值。

然后在两者之中去比较谁更接近，然后返回即可。

时间复杂度为 O(h)，注意如果你使用 in-order traversal 的话，时间复杂度会是 o(n) 并不是最优的。另外复杂度也不是 O(logn) 因为 BST 并不保证树高是 logn 的。

class Solution {     public int closestValue(TreeNode root, double target) {         if (root == null) {             return 0;         }          TreeNode lowerNode = lowerBound(root, target);         TreeNode upperNode = upperBound(root, target);          if (lowerNode == null) {             return upperNode.val;         }          if (upperNode == null) {             return lowerNode.val;         }          if (target - lowerNode.val > upperNode.val - target) {             return upperNode.val;         }          return lowerNode.val;     }      // find the node with the largest value that smaller than target     private TreeNode lowerBound(TreeNode root, double target) {         if (root == null) {             return null;         }          if (target <= root.val) {             return lowerBound(root.left, target);         }          // root.val < target         TreeNode lowerNode = lowerBound(root.right, target);         if (lowerNode != null) {             return lowerNode;         }          return root;     }      // find the node with the smallest value that larger than or equal to target     private TreeNode upperBound(TreeNode root, double target) {         if (root == null) {             return null;         }          if (root.val < target) {             return upperBound(root.right, target);         }          // root.val >= target         TreeNode upperNode = upperBound(root.left, target);         if (upperNode != null) {             return upperNode;         }          return root;     }  }  

点此查看更多题解

《九章算法班 2020 版》扩充 5 倍课时

课程亮点：

• 疫情应对版《九章算法班 2020 版》，令狐冲老师扩容 5 倍课程量

• 8 周内讲解 57 个面试核心高频考点

• 课程内容由 9 章节增加至 43 章

• 7 天视频回放，戳我查看最新课程大纲!

大佬有話說 (0)