摘要:復雜度思路用一個變量來記錄當前的值,并且在每次之前,比較得到目前的最大值。注意變量的比較不要用代碼
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);
}
}
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://m.specialneedsforspecialkids.com/yun/65253.html
Problem 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 o...
摘要:遞歸法復雜度時間空間思路根據二叉樹的性質,我們知道當遍歷到某個根節點時,最近的那個節點要么是在子樹里面,要么就是根節點本身。因為我們知道離目標數最接近的數肯定在二叉搜索的路徑上。 Closest Binary Search Tree Value I Given a non-empty binary search tree and a target value, find the va...
摘要:題目鏈接的值大小順序實際上就是滿足的條件,所以直接中序遍歷,過程中維護一個,放入個當前離最近的值,的時,新的值和的距離如果小于隊首的那個值和的距離那么移除隊首,如果,且新的距離大于等于隊首的距離,直接退出,返回隊列中的所有結果。 272. Closest Binary Search Tree Value II 題目鏈接:https://leetcode.com/problems... ...
摘要:原題網址題意在二叉搜索樹當中找到離最近的個數。解題思路由于二叉搜索數的中序遍歷是有序的,比如例子中的樹,中序遍歷為。 原題網址:https://leetcode.com/problems... Given a non-empty binary search tree and a target value, find?k?values in the BST that are closes...
摘要:解題思路對于二叉搜索樹,我們很容易會想到使用棧和隊列來解決問題,本題是要求實現一個對二叉搜索樹的遍歷器,要求每次可以返回最小的節點值,我們使用棧。 Binary Search Tree IteratorImplement an iterator over a binary search tree (BST). Your iterator will be initialized with...
閱讀 2741·2023-04-25 21:26
閱讀 1527·2021-11-25 09:43
閱讀 1960·2019-08-30 15:52
閱讀 941·2019-08-30 14:05
閱讀 2626·2019-08-29 16:10
閱讀 424·2019-08-29 13:48
閱讀 1868·2019-08-29 12:47
閱讀 1310·2019-08-23 18:04
极致性价比!云服务器续费无忧!
Tesla A100/A800、Tesla V100S等多种GPU云主机特惠2折起,不限台数,续费同价。
NVIDIA RTX 40系,高性价比推理显卡,满足AI应用场景需要。
乌兰察布+上海青浦,满足东推西训AI场景需要