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

資訊專欄INFORMATION COLUMN

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

AlphaWallet / 2873人閱讀

摘要：遞歸法復雜度時間空間思路根據二叉樹的性質，我們知道當遍歷到某個根節點時，最近的那個節點要么是在子樹里面，要么就是根節點本身。因為我們知道離目標數最接近的數肯定在二叉搜索的路徑上。

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.
遞歸法 復雜度

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

思路

根據二叉樹的性質，我們知道當遍歷到某個根節點時，最近的那個節點要么是在子樹里面，要么就是根節點本身。所以我們根據這個遞歸，返回子樹中最近的節點，和根節點中更近的那個就行了。

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

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

思路

記錄一個最近的值，然后沿著二叉搜索的路徑一路比較下去，并更新這個最近值就行了。因為我們知道離目標數最接近的數肯定在二叉搜索的路徑上。

代碼 
public class Solution {
    public int closestValue(TreeNode root, double target) {
        int closest = root.val;
        while(root != null){
            // 如果該節點的離目標更近，則更新到目前為止的最近值
            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.
中序遍歷法 復雜度

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

思路

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

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64600.html

相關文章

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

    摘要：原題網址題意在二叉搜索樹當中找到離最近的個數。解題思路由于二叉搜索數的中序遍歷是有序的，比如例子中的樹，中序遍歷為。 原題網址：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

    摘要：復雜度思路用一個變量來記錄當前的值，并且在每次之前，比較得到目前的最大值。注意變量的比較不要用代碼 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

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

    NusterCache 評論0 收藏0

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

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

    用戶84 評論0 收藏0

發表評論

0條評論

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