摘要:復(fù)雜度思路用一個變量來記錄當(dāng)前的值,并且在每次之前,比較得到目前的最大值。注意變量的比較不要用代碼
LeetCode[270] Closest Binary Search Tree Value
RecursionGiven 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.
復(fù)雜度
O(N), O(lgN)
思路
用一個變量來記錄當(dāng)前的值,并且在每次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); } }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://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...
摘要:遞歸法復(fù)雜度時間空間思路根據(jù)二叉樹的性質(zhì),我們知道當(dāng)遍歷到某個根節(jié)點時,最近的那個節(jié)點要么是在子樹里面,要么就是根節(jié)點本身。因為我們知道離目標數(shù)最接近的數(shù)肯定在二叉搜索的路徑上。 Closest Binary Search Tree Value I Given a non-empty binary search tree and a target value, find the va...
摘要:題目鏈接的值大小順序?qū)嶋H上就是滿足的條件,所以直接中序遍歷,過程中維護一個,放入個當(dāng)前離最近的值,的時,新的值和的距離如果小于隊首的那個值和的距離那么移除隊首,如果,且新的距離大于等于隊首的距離,直接退出,返回隊列中的所有結(jié)果。 272. Closest Binary Search Tree Value II 題目鏈接:https://leetcode.com/problems... ...
摘要:原題網(wǎng)址題意在二叉搜索樹當(dāng)中找到離最近的個數(shù)。解題思路由于二叉搜索數(shù)的中序遍歷是有序的,比如例子中的樹,中序遍歷為。 原題網(wǎng)址:https://leetcode.com/problems... Given a non-empty binary search tree and a target value, find?k?values in the BST that are closes...
摘要:解題思路對于二叉搜索樹,我們很容易會想到使用棧和隊列來解決問題,本題是要求實現(xiàn)一個對二叉搜索樹的遍歷器,要求每次可以返回最小的節(jié)點值,我們使用棧。 Binary Search Tree IteratorImplement an iterator over a binary search tree (BST). Your iterator will be initialized with...
閱讀 2696·2023-04-25 21:26
閱讀 1514·2021-11-25 09:43
閱讀 1949·2019-08-30 15:52
閱讀 932·2019-08-30 14:05
閱讀 2614·2019-08-29 16:10
閱讀 414·2019-08-29 13:48
閱讀 1860·2019-08-29 12:47
閱讀 1299·2019-08-23 18:04