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

資訊專欄INFORMATION COLUMN

[Leetcode] Kth Smallest Element in a BST 二叉搜索樹第k小節

Dean / 2973人閱讀

摘要：中序遍歷復雜度時間空間思路因為左節點小于根節點小于右節點，二叉搜索樹的一個特性就是中序遍歷的結果就是樹內節點從小到大順序輸出的結果。這里采用迭代形式，我們就可以在找到第小節點時馬上退出。這樣我們就可以用二叉樹搜索的方法來解決這個問題了。

Kth Smallest Element in a BST 
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.


Note:  You may assume k is always valid, 1 ≤ k ≤ BST"s total elements.


Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?


Hint:


Try to utilize the property of a BST. What if you could modify the BST node"s structure? The optimal runtime complexity is O(height of BST).
中序遍歷 復雜度

時間 O(N) 空間 O(N)

思路

因為左節點小于根節點小于右節點，二叉搜索樹的一個特性就是中序遍歷的結果就是樹內節點從小到大順序輸出的結果。這里采用迭代形式，我們就可以在找到第k小節點時馬上退出。中序遍歷詳見Binary Tree Traversal。

代碼 
public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack s = new Stack();
        while(root!=null){
            s.push(root);
            root = root.left;
        }
        while(!s.isEmpty()){
            TreeNode curr = s.pop();
            k--;
            if(k == 0) return curr.val;
            if(curr.right != null){
                curr = curr.right;
                while(curr!=null){
                    s.push(curr);
                    curr = curr.left;
                }
            }
        }
        return 0;
    }
}
后續 Follow Up

這題的難點其實在于Follow Up：如果我們頻繁的操作該樹，并且頻繁的調用kth函數，有什么優化方法使時間復雜度降低至O(h)？h是樹的高度。根據提示，我們可以在TreeNode中加入一個rank成員，這個變量記錄的是該節點的左子樹中節點的個數，其實就是有多少個節點比該節點小。這樣我們就可以用二叉樹搜索的方法來解決這個問題了。這個添加rank的操作可以在建樹的時候一起完成。

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

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

相關文章

  • [Leetcode-Tree] Kth Smallest Element in a BST

    摘要：解題思路本題需要找的是第小的節點值，而二叉搜索樹的中序遍歷正好是數值從小到大排序的，那么這題就和中序遍歷一個情況。 Kth Smallest Element in a BSTGiven a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You ...

    Carl 評論0 收藏0

  • Kth Smallest Element in a BST

    摘要：題目鏈接二分找結果，按左邊數來分如果改下，加入的，那就可以在時間內找到結果了 Kth Smallest Element in a BST 題目鏈接：https://leetcode.com/problems... inorder traverse： public class Solution { public int kthSmallest(TreeNode root, int...

    Barry_Ng 評論0 收藏0

  • leetcode 315 Count of Smaller Numbers After Self 以

    摘要：題目意思就是要一個個的返回當前的最小值。所以解法自然就是。我們需要找出被打亂的點并返回正確結果。然后將兩個不正確的點記錄下來，最后回原來正確的值。如果是葉子節點，或者只有一個子樹。思想來自于的代碼實現。 跳過總結請點這里：https://segmentfault.com/a/11... BST最明顯的特點就是root.left.val < root.val < root.right.v...

    inapt 評論0 收藏0

  • [LeetCode] 378. Kth Smallest Element in a Sorted M

    摘要：先放一行，或一列把堆頂的最小元素取出來，取次，如果該有下一行下一列的，放入堆中最小的個元素已經在上面的循環被完了，下一個堆頂元素就是 Problem Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in...

    Shihira 評論0 收藏0

  • leetcode378. Kth Smallest Element in a Sorted Matr

    摘要：因此我們可以采用部分元素堆排序即可。即我們每次只需要可能構成第個元素的值進行堆排序就可以了。 題目要求 Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix. Note that...

    dailybird 評論0 收藏0

發表評論

0條評論

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