LeetCode[270] Closest Binary Search Tree Value
文章目录
LeetCode[270] Closest Binary Search Tree Value
Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
Note:
Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.
Recursion
复杂度
O(N), O(lgN)
思路
用一个变量来记录当前的值,并且在每次recursion之前,比较得到目前的最大值。注意double变量的比较不要用==
代码
double min = Double.MAX_VALUE;
int val = 0;
public int closetValue(TreeNode root, double target) {
helper(root, target);
return val;
}
public void helper(TreeNode root, double target) {
if(root == null) return;
if(Math.abs(target - root.val) < min) {
min = Math.abs(target - root.val);
val = root.val;
}
if(root.val > target) {
helper(root.left, target);
}
else {
helper(root.right, target);
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论