国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[Leetcode] Closest Binary Search Tree Value 最近二叉搜索

AlphaWallet / 2882人閱讀

摘要：遞歸法復(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 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ù)雜度

時(shí)間 O(logN) 空間 O(H)

思路

根據(jù)二叉樹的性質(zhì)，我們知道當(dāng)遍歷到某個(gè)根節(jié)點(diǎn)時(shí)，最近的那個(gè)節(jié)點(diǎn)要么是在子樹里面，要么就是根節(jié)點(diǎn)本身。所以我們根據(jù)這個(gè)遞歸，返回子樹中最近的節(jié)點(diǎn)，和根節(jié)點(diǎn)中更近的那個(gè)就行了。

代碼 
public class Solution {
    public int closestValue(TreeNode root, double target) {
        // 選出子樹的根節(jié)點(diǎn)
        TreeNode kid = target < root.val ? root.left : root.right;
        // 如果沒有子樹，也就是遞歸到底時(shí)，直接返回當(dāng)前節(jié)點(diǎn)值
        if(kid == null) return root.val;
        // 找出子樹中最近的那個(gè)節(jié)點(diǎn)
        int closest = closestValue(kid, target);
        // 返回根節(jié)點(diǎn)和子樹最近節(jié)點(diǎn)中，更近的那個(gè)節(jié)點(diǎn)
        return Math.abs(root.val - target) < Math.abs(closest - target) ? root.val : closest;
    }
}
迭代法 復(fù)雜度

時(shí)間 O(logN) 空間 O(H)

思路

記錄一個(gè)最近的值，然后沿著二叉搜索的路徑一路比較下去，并更新這個(gè)最近值就行了。因?yàn)槲覀冎离x目標(biāo)數(shù)最接近的數(shù)肯定在二叉搜索的路徑上。

代碼 
public class Solution {
    public int closestValue(TreeNode root, double target) {
        int closest = root.val;
        while(root != null){
            // 如果該節(jié)點(diǎn)的離目標(biāo)更近，則更新到目前為止的最近值
            closest = Math.abs(closest - target) < Math.abs(root.val - target) ? closest : root.val;
            // 二叉搜索
            root = target < root.val ? root.left : root.right;
        }
        return closest;
    }
}
Closest Binary Search Tree Value II 
Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.


Note: Given target value is a floating point. You may assume k is always valid, that is: k ≤ total nodes. You are guaranteed to have only one unique set of k values in the BST that are closest to the target. Follow up: Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?


Hint:


Consider implement these two helper functions: getPredecessor(N), which returns the next smaller node to N. getSuccessor(N), which returns the next larger node to N.
中序遍歷法 復(fù)雜度

時(shí)間 O(N) 空間 Max(O(K),O(H))

思路

二叉搜索樹的中序遍歷就是順序輸出二叉搜索樹，所以我們只要中序遍歷二叉搜索樹，同時(shí)維護(hù)一個(gè)大小為K的隊(duì)列，前K個(gè)數(shù)直接加入隊(duì)列，之后每來一個(gè)新的數(shù)（較大的數(shù)），如果該數(shù)和目標(biāo)的差，相比于隊(duì)頭的數(shù)離目標(biāo)的差來說，更小，則將隊(duì)頭拿出來，將新數(shù)加入隊(duì)列。如果該數(shù)的差更大，則直接退出并返回這個(gè)隊(duì)列，因?yàn)楹竺娴臄?shù)更大，差值也只會(huì)更大。

代碼 
public class Solution {
    public List closestKValues(TreeNode root, double target, int k) {
        Queue klist = new LinkedList();
        Stack stk = new Stack();
        // 迭代中序遍歷二叉搜索樹的代碼
        while(root != null){
            stk.push(root);
            root = root.left;
        }
        while(!stk.isEmpty()){
            TreeNode curr = stk.pop();
            // 維護(hù)一個(gè)大小為k的隊(duì)列
            // 隊(duì)列不到k時(shí)直接加入
            if(klist.size() < k){
                klist.offer(curr.val);
            } else {
            // 隊(duì)列到k時(shí)，判斷下新的數(shù)是否更近，更近就加入隊(duì)列并去掉隊(duì)頭
                int first = klist.peek();
                if(Math.abs(first - target) > Math.abs(curr.val - target)){
                    klist.poll();
                    klist.offer(curr.val);
                } else {
                // 如果不是更近則直接退出，后面的數(shù)只會(huì)更大
                    break;
                }
            }
            // 中序遍歷的代碼
            if(curr.right != null){
                curr = curr.right;
                while(curr != null){
                    stk.push(curr);
                    curr = curr.left;
                }
            }
        }
        // 強(qiáng)制轉(zhuǎn)換成List，是用LinkedList實(shí)現(xiàn)的所以可以轉(zhuǎn)換
        return (List)klist;
    }
}

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/64600.html

相關(guān)文章

  • 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 評(píng)論0 收藏0

  • LeetCode[270] Closest Binary Search Tree Value

    摘要：復(fù)雜度思路用一個(gè)變量來記錄當(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 close...

    pumpkin9 評(píng)論0 收藏0

  • [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 評(píng)論0 收藏0

  • 272. Closest Binary Search Tree Value II

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

    NusterCache 評(píng)論0 收藏0

  • LeetCode 之 JavaScript 解答第98題 —— 驗(yàn)證二叉搜索樹

    摘要：小鹿題目驗(yàn)證二叉搜索樹給定一個(gè)二叉樹，判斷其是否是一個(gè)有效的二叉搜索樹。假設(shè)一個(gè)二叉搜索樹具有如下特征節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。算法思路定義全局的變量，用來返回是否為二叉搜索樹。 Time：2019/4/24Title: Vaildata Binary Search TreeDifficulty: MediumAuthor: 小鹿 ...

    用戶84 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<