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

資訊專欄INFORMATION COLUMN

[Leetcode-Tree] Kth Smallest Element in a BST

Carl / 913人閱讀

摘要：解題思路本題需要找的是第小的節(jié)點值，而二叉搜索樹的中序遍歷正好是數(shù)值從小到大排序的，那么這題就和中序遍歷一個情況。

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

1.解題思路

本題需要找的是第k小的節(jié)點值，而二叉搜索樹的中序遍歷正好是數(shù)值從小到大排序的，那么這題就和中序遍歷一個情況。

public class Solution {
    Stack s=new Stack();
    public int kthSmallest(TreeNode root, int k) {
        if(root==null) return 0;
        pushLeft(root);
        while(!s.empty()){
            TreeNode node=s.pop();
            if(--k==0) return node.val;
            if(node.right!=null)
                pushLeft(node.right);
        }
        return 0;
    }
    private void pushLeft(TreeNode root){
        TreeNode node=root;
        while(node!=null){
            s.push(node);
            node=node.left;
        }
    }
}

3.Follow up

如果樹會經(jīng)常被更改，為了效率，我們可以對樹的構(gòu)造稍作變更，添加一個屬性，來標明該節(jié)點擁有的左子樹的節(jié)點數(shù)，而這個Number就是比當前值小的節(jié)點個數(shù)，這樣我們結(jié)合二分法，就很容易找到第k個小的節(jié)點值。

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

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

相關(guān)文章

  • [Leetcode] Kth Smallest Element in a BST 二叉搜索樹第k小節(jié)

    摘要：中序遍歷復雜度時間空間思路因為左節(jié)點小于根節(jié)點小于右節(jié)點，二叉搜索樹的一個特性就是中序遍歷的結(jié)果就是樹內(nèi)節(jié)點從小到大順序輸出的結(jié)果。這里采用迭代形式，我們就可以在找到第小節(jié)點時馬上退出。這樣我們就可以用二叉樹搜索的方法來解決這個問題了。 Kth Smallest Element in a BST Given a binary search tree, write a function...

    Dean 評論0 收藏0

  • Kth Smallest Element in a BST

    摘要：題目鏈接二分找結(jié)果，按左邊數(shù)來分如果改下，加入的，那就可以在時間內(nèi)找到結(jié)果了 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 以

    摘要：題目意思就是要一個個的返回當前的最小值。所以解法自然就是。我們需要找出被打亂的點并返回正確結(jié)果。然后將兩個不正確的點記錄下來，最后回原來正確的值。如果是葉子節(jié)點，或者只有一個子樹。思想來自于的代碼實現(xiàn)。 跳過總結(jié)請點這里：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

    摘要：先放一行，或一列把堆頂?shù)淖钚≡厝〕鰜?，取次，如果該有下一行下一列的，放入堆中最小的個元素已經(jīng)在上面的循環(huán)被完了，下一個堆頂元素就是 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

  • 378. Kth Smallest Element in a Sorted Matrix

    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 it is the kth smallest element in the sorted order, not the...

    makeFoxPlay 評論0 收藏0

發(fā)表評論

0條評論

Carl

男|高級講師

TA的文章

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