成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

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

AlphaWallet / 2880人閱讀

摘要：遞歸法復(fù)雜度時間空間思路根據(jù)二叉樹的性質(zhì)，我們知道當(dāng)遍歷到某個根節(jié)點(diǎn)時，最近的那個節(jié)點(diǎn)要么是在子樹里面，要么就是根節(jié)點(diǎn)本身。因為我們知道離目標(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ù)雜度

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

思路

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

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

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

思路

記錄一個最近的值，然后沿著二叉搜索的路徑一路比較下去，并更新這個最近值就行了。因為我們知道離目標(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ù)雜度

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

思路

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

代碼 
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ù)一個大小為k的隊列
            // 隊列不到k時直接加入
            if(klist.size() < k){
                klist.offer(curr.val);
            } else {
            // 隊列到k時，判斷下新的數(shù)是否更近，更近就加入隊列并去掉隊頭
                int first = klist.peek();
                if(Math.abs(first - target) > Math.abs(curr.val - target)){
                    klist.poll();
                    klist.offer(curr.val);
                } else {
                // 如果不是更近則直接退出，后面的數(shù)只會更大
                    break;
                }
            }
            // 中序遍歷的代碼
            if(curr.right != null){
                curr = curr.right;
                while(curr != null){
                    stk.push(curr);
                    curr = curr.left;
                }
            }
        }
        // 強(qiáng)制轉(zhuǎn)換成List，是用LinkedList實現(xiàn)的所以可以轉(zhuǎn)換
        return (List)klist;
    }
}

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64600.html

相關(guān)文章

  • LeetCode 272 Closest Binary Tree Traversal II 解題思路

    摘要：原題網(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...

    Youngdze 評論0 收藏0

  • LeetCode[270] Closest Binary Search Tree Value

    摘要：復(fù)雜度思路用一個變量來記錄當(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 評論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 評論0 收藏0

  • 272. Closest Binary Search Tree Value II

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

    NusterCache 評論0 收藏0

  • LeetCode 之 JavaScript 解答第98題 —— 驗證二叉搜索樹

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

    用戶84 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<