LeetCode 솔루션 분류
230. Kth Smallest Element in a BST
본문
[ LeetCode 시즌 3 ] 2022년 4월 17일 문제입니다
https://leetcode.com/problems/kth-smallest-element-in-a-bst/
[Medium] 230. Kth Smallest Element in a BST
Given the root
of a binary search tree, and an integer k
, return the kth
smallest value (1-indexed) of all the values of the nodes in the tree.
Example 1:
Input: root = [3,1,4,null,2], k = 1 Output: 1
Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3 Output: 3
Constraints:
- The number of nodes in the tree is
n
. 1 <= k <= n <= 104
0 <= Node.val <= 104
Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?
관련자료
-
링크
댓글 3
mingki님의 댓글
- 익명
- 작성일
C++
Runtime: 30 ms, faster than 29.91% of C++ online submissions for Kth Smallest Element in a BST.
Memory Usage: 24.1 MB, less than 61.00% of C++ online submissions for Kth Smallest Element in a BST.
Runtime: 30 ms, faster than 29.91% of C++ online submissions for Kth Smallest Element in a BST.
Memory Usage: 24.1 MB, less than 61.00% of C++ online submissions for Kth Smallest Element in a BST.
class Solution {
int res = 0;
int curr = 0;
private:
void helper(TreeNode *root, int k) {
if (root) {
helper(root->left, k);
res = ++curr == k ? root->val : res;
helper(root->right, k);
}
}
public:
int kthSmallest(TreeNode* root, int k) {
helper(root, k);
return res;
}
};
9dea0936님의 댓글
- 익명
- 작성일
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
head = root
self.ans = 0
self.idx = 0
def quickSearch(node):
if not node:
return
quickSearch(node.left)
self.idx += 1
if self.idx == k:
self.ans = node.val
quickSearch(node.right)
quickSearch(head)
return self.ans
bobkim님의 댓글
- 익명
- 작성일
Runtime: 27 ms, faster than 41.30% of C++ online submissions for Kth Smallest Element in a BST.
Memory Usage: 24.2 MB, less than 61.00% of C++ online submissions for Kth Smallest Element in a BST.
Memory Usage: 24.2 MB, less than 61.00% of C++ online submissions for Kth Smallest Element in a BST.
class Solution {
public:
int counter=0;
int knum;
TreeNode* p_ans;
void findKth(TreeNode* &root){
if(root->left != nullptr){
findKth(root->left);
}
counter++;
if(counter == knum){
p_ans=root;
return;
}
if(root->right != nullptr){
findKth(root->right);
}
return ;
};
int kthSmallest(TreeNode* root, int k) {
knum=k;
findKth(root);
return p_ans->val;
}
};