資訊專欄INFORMATION COLUMN
摘要：中序遍歷復(fù)雜度時間空間思路因為左節(jié)點小于根節(jié)點小于右節(jié)點，二叉搜索樹的一個特性就是中序遍歷的結(jié)果就是樹內(nèi)節(jié)點從小到大順序輸出的結(jié)果。這里采用迭代形式，我們就可以在找到第小節(jié)點時馬上退出。這樣我們就可以用二叉樹搜索的方法來解決這個問題了。
Kth Smallest Element in a BST
中序遍歷 復(fù)雜度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)
思路因為左節(jié)點小于根節(jié)點小于右節(jié)點，二叉搜索樹的一個特性就是中序遍歷的結(jié)果就是樹內(nèi)節(jié)點從小到大順序輸出的結(jié)果。這里采用迭代形式，我們就可以在找到第k小節(jié)點時馬上退出。中序遍歷詳見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;
}
}
后續(xù) Follow Up
這題的難點其實在于Follow Up：如果我們頻繁的操作該樹，并且頻繁的調(diào)用kth函數(shù)，有什么優(yōu)化方法使時間復(fù)雜度降低至O(h)？h是樹的高度。根據(jù)提示，我們可以在TreeNode中加入一個rank成員，這個變量記錄的是該節(jié)點的左子樹中節(jié)點的個數(shù)，其實就是有多少個節(jié)點比該節(jié)點小。這樣我們就可以用二叉樹搜索的方法來解決這個問題了。這個添加rank的操作可以在建樹的時候一起完成。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64482.html
摘要：解題思路本題需要找的是第小的節(jié)點值，而二叉搜索樹的中序遍歷正好是數(shù)值從小到大排序的，那么這題就和中序遍歷一個情況。 Kth Smallest Element in a BSTGiven a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You ...
摘要：題目鏈接二分找結(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...
摘要：題目意思就是要一個個的返回當(dāng)前的最小值。所以解法自然就是。我們需要找出被打亂的點并返回正確結(jié)果。然后將兩個不正確的點記錄下來，最后回原來正確的值。如果是葉子節(jié)點，或者只有一個子樹。思想來自于的代碼實現(xiàn)。 跳過總結(jié)請點這里：https://segmentfault.com/a/11... BST最明顯的特點就是root.left.val < root.val < root.right.v...
摘要：先放一行，或一列把堆頂?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...
摘要：因此我們可以采用部分元素堆排序即可。即我們每次只需要可能構(gòu)成第個元素的值進行堆排序就可以了。 題目要求 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...
閱讀 3542·2021-10-09 09:41
閱讀 2745·2021-10-08 10:18
閱讀 2183·2021-09-10 10:51
閱讀 2680·2021-09-10 10:50
閱讀 776·2021-09-09 09:33
閱讀 3383·2021-09-06 15:14
閱讀 3017·2019-08-30 11:06
閱讀 3248·2019-08-29 14:04
