LeetCode[270] Closest Binary Search Tree Value

pumpkin9 發(fā)布于2019-08-14 15:02 / 1625人閱讀

摘要：復(fù)雜度思路用一個(gè)變量來(lái)記錄當(dāng)前的值，并且在每次之前，比較得到目前的最大值。注意變量的比較不要用代碼

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

復(fù)雜度
O(N), O(lgN)

思路
用一個(gè)變量來(lái)記錄當(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);
    }
}

GPU云服務(wù)器云服務(wù)器 binary-search-tree binary-tree binary-search n270 linux

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/65253.html

相關(guān)文章

[LeetCode] 270. Closest Binary Search Tree Value

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...

XUI 2019-08-16 13:49 評(píng)論0 收藏0
[Leetcode] Closest Binary Search Tree Value 最近二叉搜索

摘要：遞歸法復(fù)雜度時(shí)間空間思路根據(jù)二叉樹的性質(zhì)，我們知道當(dāng)遍歷到某個(gè)根節(jié)點(diǎn)時(shí)，最近的那個(gè)節(jié)點(diǎn)要么是在子樹里面，要么就是根節(jié)點(diǎn)本身。因?yàn)槲覀冎离x目標(biāo)數(shù)最接近的數(shù)肯定在二叉搜索的路徑上。 Closest Binary Search Tree Value I Given a non-empty binary search tree and a target value, find the va...

AlphaWallet 2019-08-14 12:37 評(píng)論0 收藏0
272. Closest Binary Search Tree Value II

摘要：題目鏈接的值大小順序?qū)嶋H上就是滿足的條件，所以直接中序遍歷，過(guò)程中維護(hù)一個(gè)，放入個(gè)當(dāng)前離最近的值，的時(shí)，新的值和的距離如果小于隊(duì)首的那個(gè)值和的距離那么移除隊(duì)首，如果，且新的距離大于等于隊(duì)首的距離，直接退出，返回隊(duì)列中的所有結(jié)果。 272. Closest Binary Search Tree Value II 題目鏈接：https://leetcode.com/problems... ...

NusterCache 2019-08-14 17:35 評(píng)論0 收藏0
LeetCode 272 Closest Binary Tree Traversal II 解題思路

摘要：原題網(wǎng)址題意在二叉搜索樹當(dāng)中找到離最近的個(gè)數(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...

Youngdze 2019-08-16 13:26 評(píng)論0 收藏0
[Leetcode - Tree] Binary Search Tree Iterator

摘要：解題思路對(duì)于二叉搜索樹，我們很容易會(huì)想到使用棧和隊(duì)列來(lái)解決問(wèn)題，本題是要求實(shí)現(xiàn)一個(gè)對(duì)二叉搜索樹的遍歷器，要求每次可以返回最小的節(jié)點(diǎn)值，我們使用棧。 Binary Search Tree IteratorImplement an iterator over a binary search tree (BST). Your iterator will be initialized with...

jsyzchen 2019-08-16 10:26 評(píng)論0 收藏0